링크드 리스트 (Linked List)

 

 

배경

 

 

기존 배열은 고정된 크기를 가지고 있었고, 이 부분을 개선하기 위해 자동으로 크기가 관리되는 동적 배열의 필요성이 확대됐고, 링크드리스트가 도입됐다.

 

 

싱글 링크드 리스트 (Singly Linked List)

 

 

데이터가 추가될 때 마다 데이터와 다음 데이터의 주소를 생성한다. 

 

미리 데이터 공간을 할당하지 않고 사용할 수 있어 편리하지만, 데이터들을 연속적으로 이어 주기 위해 다음 데이터의 주소를 담고 있는 데이터 공간을 사용해야 해서 저장공간의 효율은 좋지 않으며,  같은 이유로 데이터에 접근하는 속도도 기존 배열보다 느리다.

 

또한 중간에 끼어 있는 데이터를 삭제할 때도 앞뒤 데이터의 연결을 재구성해야 하는 등 추가 작업이 필요하다.

// 코드 추가 예정

 

 

이중 링크드 리스트 (Doubly Linked List)

 

 

기본 링크드 리스트를 사용하면 뒷부분의 인덱스를 참조하려고 할 때 첫 부분부터 순차적으로 접근해야 하기 때문에 효율적이지 않다.

이런 문제를 해결하기 위해 이중 링크드 리스트가 도입됐다.

 

이중 링크드 리스트에서는 하나의 데이터에 다음 데이터에 대한 정보 뿐만 아니라 이전 데이터에 대한 정보도 함께 저장해 앞에서부터 탐색을 진행할 수도 있고, 뒤에서부터 탐색을 진행할 수 있도록 설계됐다.

// 코드 추가 예정

 

 

 

 

 

 

 

그림과 같이 링크드 리스트에는 메모리부터 할당받은 공간인 데이터를 저장하는 공간이 있고, 공간들을 연결하는 링크로 구성된다. (포인터)

 

구현할 때는 노드 클래스를 만들고 데이터와 포인터 변수를 만들어 사용한다.

 

데이터를 다룰 때 삽입과 제거가 필요한 경우 링크드 리스트를 사용하는 편이 합리적이다. 

삽입과 제거를 진행하면서 동적으로 크기가 관리되기 때문에 배열보다 훨씬 간편하다.

 

하지만, 특정 위치의 데이터를 읽어올 때는 링크드리스트의 구조 상 비효율적이다.

 

배열과 링크드리스트의 시간복잡도에 대해서는 위 표를 참고하자.

 

 

가장 기본적인 링크드리스트는 ArrayList이다.