[자료구조]링크드 리스트(Linked List)

링크드 리스트 (Linked List)

링크드 리스트(Linked List), 연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 됩니다.

 

 

특징

• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조입니다.
• 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조입니다.
• 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원합니다.
• 장점
  • 배열은 미리 데이터의 공간을 할당해야하지만 링크드 리스트는 미리 데이터 공간을 미리 할당하지 않아도 됩니다.
• 단점
  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 낮습니다.
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느립니다.
  • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요합니다.
• 링크드 리스트 기본 구조와 용어
  • 노드(Node): 데이터 저장 단위 (데이터 값, 포인터)로 구성되어 있습니다.
  • 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간입니다. 

 

 

 

다양한 링크드 리스트 구조

더블 링크드 리스트(Doubly linked list)

• 이중 연결 리스트라고도 부릅니다.
• 장점
  • 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능합니다.

 

원형 링크드 리스트(Circular linked list)

• 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트입니다.
• 장점
  • 반복적인 순회에서 연결리스트의 끝을 체크해야 할 필요가 없습니다. 또한 HEAD와 같은 메타데이터가 필요하지 않기 때문에 시간, 메모리의 효율이 높습니다.