[자료구조 리스트] 연결 리스트(Linked List)

  단순 연결 리스트(Singly Linked List)란 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조입니다. 즉, 동적 메모리 할당을 받아 노드(Node)를 만들고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결합니다. 노드마다 레퍼런스를 저장할 공간이 필요합니다. 각 노드 객체마다 항목을 저장할 item과 Node 레퍼런스를 저장하는 next를 가집니다. 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않습니다. 크기를 예측하지 않으므로 빈 공간이 존재하지 않습니다. 단순 연결 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵습니다. 이를 보완한 이중 연결 리스트(Doubly Linked List)가 있습니다.

  연결 리스트에서 항목을 접근 또는 탐색하려면 항상 첫 노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차 탐색(Sequential Search)을 해야만 합니다. 따라서 O(n) 시간이 필요합니다. 그러나 삽입이나 삭제 시 항목들의 이동이 필요하지 않습니다. 각각 상수 개의 레퍼런스를 갱신하므로 O(1) 시간이 필요합니다. 그러나 insertAfter 또는 deleteAfter의 경우 특정 노드 p의 레퍼런스가 주어지지만, p가 주어지지 않는 삽입 또는 삭제는 head로부터 p를 찾기 위해 리스트를 탐색해야 하므로 O(n) 시간이 걸립니다.

  순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠릅니다. 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠릅니다.

  연결 리스트의 개념을 확장한 트리라는 자료구조가 있습니다.

 

  연결 리스트에서의 용어

• 노드(node): 요소
• next: 자신과 연결된 다음 요소에 대한 참조(주소값)

 

  연결 리스트의 장단점

• 장점
  • 데이터 공간을 미리 할당할 필요가 없음
  • 리스트의 길이가 가변적이기 때문에 데이터의 추가와 삭제 시 용이함
• 단점
  • 연결구조를 위한 별도의 데이터 공간 필요
  • 순차 탐색
  • 데이터 추가 및 삭제 시에 데이터의 연결을 재구성하는 작업이 필요함

 

 

  ※ "자바와 함께하는 자료구조의 이해", "자바의 정석"이라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.