연결 리스트

Linked List

• 선형의 자료 구조
• 요소들이 연속적인 메모리 공간에 저장된 것이 아니다
  
  
• 각각의 요소들은 pointer로 연결되어 있다
  
  
• 연결 리스트의 순서는 각 요소의 pointer에 의해 결정된다.
• 첫 번째 노드를 head라고 한다.
  
  연결 리스트가 비어있으면 head는 NULL이다.
  
  
• 마지막 노드를 tail이라고 한다.

Algorithms by Robert Sedgew

 

VS array

배열과 연결 리스트는 선형의 자료 구조로 비슷한 점이 많지만 

 

다른 점이 두 가지 있다.

 

• 크기
  
  • 배열의 크기는 고정되어 있지만,
    
    연결 리스트의 크기는 유동적이다.
• 삽입/삭제
  • 배열은 삽입 및 삭제가 비싼 작업이라고 할 수 있다.
    
    크기와도 연관되는 이야기로 크기가 고정되어 있으므로
    
    새로운 요소를 삽입하려면 새로운 공간을 만들어야 하기 때문이다.
    
• 조회
  • 연결 리스트는 원하는 인덱스를 바로 조회할 수 없다.
    
    첫 번째 노드부터 순서대로 찾아가야 하기 때문이다.

연결 리스트는 pointer를 위한 메모리가 필요하고 캐시와 같이 작업하기도 불편하다.

 

연결 리스트의 종류

1. 단일 연결 리스트
   각 요소는 key와 next pointer를 가진다.
   
   
2. 이중 연결 리스트
   단일 연결 리스트는 다시 앞으로 갈 수 없으므로
   
   이중 연결 리스트를 사용한다.
   
   각 요소는 key와 prev, next pointer를 가진다.
   
   
3. 원형 연결 리스트
   head의 prev가 tail을 가리키고
   
   tail의 next가 head를 가리킨다.
   
   
4. sorted
   
   key를 순서대로 정렬한 연결 리스트
   
   
5. unsorted

 

L은 linked list, k는 요소의 key

조회

list-search(L, k)

x = L.head
while x != NULL and x.key != k
	x = x.next
return x

 

연결 리스트 L의 노드들 중에서 k를 키로 가지는 첫 번째 노드를 찾는다.

 

연결 리스트는 첫 노드부터 순서대로 조회해야 하기 때문에 비효율적이다.

 

O(n)

 

 

삽입

list-insert(L, x)

x.next = L.head
if L.head != NULL
	L.head.prew = x
L.head = x
x.prev = NULL

연결 리스트 헤드에 새로운 데이터가 삽입된다.

 

새로 삽입하는 노드의 next가 기존의 head를 가리킨다.

 

삽입하고자 하는 위치가 정해져 있지 않다면 시간은 O(1)

 

원하는 위치가 있다면 조회를 먼저 해야 한다.

 

삭제

list-delete(L, x)

if x.prev != NULL
	x.prev.next = x.next
else L.head = x.next
if x.next != NULL
	x.next.prev = x.prev

연결 리스트 헤드가 삭제된다.

 

삭제하고 하는 위치가 정해져 있다면 조회를 먼저 해야 한다.