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

연결 리스트(linked list) 자료구조는 선형으로 그룹화된 데이터의 집합으로 데이터와 다음 데이터의 주소를 포함하고 있는 하나의 노드가 선형으로 연결된 자료구조이다.

 

 예를 들어, 보물 찾기를 한다면 힌트 메모지 하나하나를 노드로 만들고 첫 번째 힌트 메모지에는 다음 메모지가 어디 있는지를 표시해 놓는 방식이다.

 

<출처> 나무위키

 

특징

 

• 배열에 비해 노드의 추가와 삭제가 용이하다.
  
  
• 노드가 메모리에 흩어져 있어서 특정 노드로 쉽게 접근할 수 없다. 즉, 노드의 값을 찾으려면 전체를 순회해야 할 수도 있다.
  
  
• 배열은 데이터에 접근하는데 O(1)의 시간 복잡도를 가지지만, 연결 리스트는 최악의 경우에 O(n)의 시간 복잡도를 갖는다.

 

 

 

 

종류

 

• 단순 연결 리스트(Singly Linked List)
  : 다음 노드에 대한 참조만을 갖는 가장 단순한 형태이다. 보통 큐를 구현할 때 사용한다.
  
  
• 이중 연결 리스트(Doubly Linked List)
  : 다음 노드뿐만 아니라 이전 노드의 참조도 같이 가리키는 형태이다. 단순 연결 리스트보다 탐색이나 삭제가 용이하지만, 관리해야 할 참조가 두 개이기 때문에 삽입이나 정렬의 경우 작업량이 더 많고 자료구조의 크기가 약간 더 커진다.
  
  
• 원형 연결 리스트(Circular Linked List)
  : 단순 연결 리스트에서 마지막 원소가 null 대신 처음 원소를 가리키는 형태이다. 이중 연결 리스트의 처음과 끝을 이으면 이중 원형 연결 리스틀르 만들 수 있다. 스트림 버퍼의 구현에 많이 사용하며, 큐를 구현하는 데에도 적합하다.
  
  
• 청크 리스트(Chunked List)
  : 배열과 리스트의 장점을 합한 것으로, 리스트의 멤버가 배열이다.

 

 

 

 

사용

 

• 삽입과 삭제가 중요한 곳에 활용된다.
  
  
• 동적 기억장소 관리(dynamic storage management)
  : 실행되는 작업에 필요한 크기만큼의 메모리를 할당하는 방법에 활용된다.
  
  
• Garbage collection
  : 참조자료형의 데이터 타입을 관리하는 알고리즘 중 하나로 활용된다.

 

 

 

 

연결 리스트 - 나무위키