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

리스트란

여러 원소들을 연결하여 저장하는 자료구조를 말한다. 연속된 공간 내에 물리적으로 연결되어 있을 수도 있고, 비연속적인 공간 내에 논리적으로 연결되어 있을 수도 있다. Array 혹은 Linked List로 구현한다.

 

Array List

- 내부적으로 배열을 운영하여 연속적 공간에 원소를 저장한다.

- 장점

 1) 배열을 운영하기 때문에 인덱스로 접근하는 것이 O(1) 만에 이루어진다. (Random Access 가능)

 2) 직관적이고 간단하다.

- 단점

 1) 삽입/삭제에 shift가 필요하기 때문에 O(n)이 걸린다.

 2) 배열의 고정된 크기를 넘어서는 경우 copy가 필요하다.

 

Linked List

- 내부적으로 포인터를 가진 구조체들을 운영하여 비연속적인 공간에 논리적으로 연결된 원소들을 저장한다.

- 장점

 1) shift op이 필요하지 않아 삽입/삭제에 O(1)이 걸린다.

 2) 고정된 크기가 없으므로 Array list에서 필요한 것과 같은 copy가 필요하지 않다.

- 단점

 1) 포인터를 조정하는 시간과 포인터를 저장하는 공간이 필요하기 때문에 시공간적 오버헤드가 존재한다.

 2) Random Access가 어렵다. 인덱스로 접근하기 위해서는 O(n)이 걸리며 인덱스 위치에 삽입하는 것도 마찬가지다.

     (결과적으로 삽입과 삭제에는 O(n)이 걸리게 되지만, 트리 구조를 가진 자료구조(힙이나 binary tree, RB tree ...)를 구현하는 데에 유용하게 사용되기 때문에 중요한 자료구조이다.)

 

Linked List의 여러 가지 구현 방법

1. 일반적인 모습

여기에서 head 값만 저장하면 리스트에 접근 가능해진다.

- 단점 : 맨 앞에 원소를 삽입/삭제할 때, prev node가 존재하지 않으므로 따로 처리해야 한다.

   - 중간과 맨 끝 삽입 : 새로운 노드의 next pointer를 prev node의 next pointer로 두고, prev node의 next pointer를 자신으로

   - 맨 앞 삽입 : 새로운 노드의 next pointer를 head pointer로 두고, head pointer를 새로운 노드로

 

2. Dummy head 버전

- 장점 : 삽입/삭제 코드를 하나로 할 수 있다.

 

3. Doubly linked list 버전

- 장점 : 양쪽으로 접근 가능하므로 때때로 뒤쪽에서부터의 search가 유리할 때 유용하게 사용될 수 있다.

- 단점 : 포인터를 두개 담고 있으므로 추가적인 시간과 공간이 필요하다.

 

4. Circular 버전(Circular doubly linked list with dummy head)

- 장점 : NULL포인터를 확인할 필요가 없고, 머리에서 바로 꼬리로 가는 traverse가 편리하다.