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

정의

메모리의 불연속적인 위치에 각각의 데이터와 함께 다음 데이터의 주소를 저장하는 자료구조

 

연결 리스트에는 단순하게 하나의 노드에 데이터와 함께 다음 데이터의 주소만 포함하는 단일 연결 리스트, 다음 데이터의 주소와 이전 데이터의 주소까지 포함하는 이중 연결 리스트, 그리고 리스트 끝과 처음이 연결되어 있는 원형 연결 리스트가 있다.

 

특징

• 임의의 위치에 있는 노드의 데이터를 확인/변경하는 데 O(N)의 시간이 걸린다
  • 처음 노드에서부터 확인/변경할 노드까지 순차적으로 접근해야 한다
• 임의의 위치에 노드를 추가 / 제거하는 데 O(1)의 시간이 걸린다
  • 단, 임의의 위치에 대한 주소를 알고 있어야 한다 (해당 위치 주소를 모르면 처음 노드부터 O(N)의 시간으로 접근해야 함)
  • 단순히 노드가 가리키는 다음 주소(또는 이전 주소)를 변경하면 된다
• 추가적인 메모리 공간이 필요하다
  • 데이터 뿐만 아니라 다음 데이터(또는 이전 데이터)의 주소를 포함하기 때문에 이 주소에 대한 공간이 추가로 필요하다
  • 추가로 필요한 메모리 공간은 데이터의 개수(N)에 비례한다 (32비트 컴퓨터 : 4N 바이트, 64비트 컴퓨터: 8N 바이트)
• 캐시 적중률이 낮다
  • 데이터들이 연속된 위치에 있지 않아 다음에 쓸 데이터를 미리 예측하기가 어렵다
• 메모리에 연속적으로 배치하지 않아도 되기 때문에 할당이 쉽다