자료구조 : Linked List

Stack, Queue 에 이어서 Linked List.

사실 이걸 먼저 포스팅 했어야 되는데 ㅡ_ㅡ; 어쩌다보니 순서가 바꼈다.

<< Linked List >>

(1) 포인터를 이용하여 데이터를 저장한다.

(2) Array 와는 다르게 물리적 구조가 순차적이지 않다.

Array 의 경우, 메모리에 순차적으로 저장되지만 

Linked List 는 포인터를 이용하기 때문에 데이터가 메모리에 순차적으로 저장되어 있지 않다.

(3) Linked List 의 기본 단위는 Node 구조체로 이루어져 있다.

Node 구조체에 데이터와 Link 를 저장해놓는다.

(4) 각 Node 의 생성은 동적 할당으로 이루어지고, 

첫번째 Node 를 가르키는 노드인 Header Node 가 존재한다.

(5) Linked List 에는 3가지 종류가 있다.

- Single Linked List / Circular Linked List / Double Linked List

- 각 리스트 별로 삽입(Insert), 삭제(Remove) 연산이 있고, 

각 연산 별로 Header / Middle / Tail 에서 일어나는 경우를 살펴볼 것이다.

(이미지 출처 : http://blog.naver.com/zkd1750/90183988309)

연산 처리 과정을 그림으로 이해하기 쉽게 정리하면 좋겠지만

이미 다 배운 내용을 정리하는 차원이라 굳이 그리지는 않겠다. 귀찮다.

1. Single Linked List

(1) Insert

- Header

[Head] -> [A] -> [B] -> [C:Tail]  이런 상태에서

[Head] -> [?] -> [A] -> [B] -> [C:Tail] 로 [?] 라는 노드를 삽입할 것이다.

방법은 간단하다. 다음과 같은 순서로 노드의 삽입이 이루어진다.

① [?].next = [Head].next

② [Head].next = [?]

- Middle

[Head] -> [A] -> [B] -> [C:Tail]  이런 상태에서

[Head] -> [A] -> [B] -> [?] -> [C:Tail] 로 [?] 라는 노드를 삽입할 것이다.

① [?].next = [B].next

② [B].next = [?]

- Tail

[Head] -> [A] -> [B] -> [C:Tail]  이런 상태에서

[Head] -> [A] -> [B] -> [C] -> [?:Tail] 로 [?] 라는 노드를 삽입할 것이다.

① [C:Tail].next = [?]

② [?].next = NULL

(1번과 2번의 순서가 바뀌어도 상관은 없다.)

③ *tail = [?]

(2) Remove

- Header

[Head] -> [A] -> [B] -> [C:Tail]  이런 상태에서 [A] 를 삭제하면,

[Head] -> [B] -> [C:Tail]  이렇게 된다.

① [Head].next = [A].next    또는    [Head].next = [Head].next.next

② [A].next = NULL    // ① 연산으로 [A]를 가르키는 노드가 없으니 ① 연산 전에 [A]를 따로 저장

③ free([A])

- Middle

[Head] -> [A] -> [B] -> [C:Tail]  이런 상태에서 [B] 를 삭제하면,

[Head] -> [A] -> [C:Tail]  이렇게 된다.

① [A].next = [B].next    또는    [A].next = [A].next.next

② [B].next = NULL    // ① 연산으로 [B]를 가르키는 노드가 없으니 ① 연산 전에 [B]를 따로 저장

③ free([B])

- Tail

[Head] -> [A] -> [B] -> [C:Tail]  이런 상태에서 [C:Tail] 를 삭제하면,

[Head] -> [A] -> [B:Tail]  이렇게 된다.

① free([B].next)    // next 가 tail 인 녀석을 찾아서 메모리 해제

② [B].next = NULL

③ *tail = [B]

2. Circular Linked List

(1) Insert

- Header

[Head] -> [A] -> [B] -> [C:Tail] -> [A]  이런 상태에서

[Head] -> [?] -> [A] -> [B] -> [C:Tail] -> [?] 로 [?] 라는 노드를 삽입할 것이다.

① [?].next = [Head].next

② [Head].next = [?]

③ [C:Tail].next = [?]

- Middle

S.L.L 와 동일하다.

- Tail

[Head] -> [A] -> [B] -> [C:Tail] -> [A]  이런 상태에서

[Head] -> [A] -> [B] -> [C] -> [?:Tail] -> [A] 로 [?] 라는 노드를 삽입할 것이다.

① [?].next = [C:Tail].next    또는    [?].next = [Head].next

② [C:Tail].next = [?]

③ *tail = [?]

(2) Remove

- Header

[Head] -> [A] -> [B] -> [C:Tail] -> [A]  이런 상태에서 [A] 를 삭제하면,

[Head] -> [B] -> [C:Tail] -> [B]  이렇게 된다.

① [Head].next = [A].next    또는    [Head].next = [Head].next.next

② [C:Tail] = [Head].next

③ [A].next = NULL    // ① 연산으로 [A]를 가르키는 노드가 없으니 ① 연산 전에 [A]를 따로 저장

④ free([A])

- Middle

S.L.L 와 동일하다.

- Tail

[Head] -> [A] -> [B] -> [C:Tail] -> [A]  이런 상태에서 [C:Tail] 를 삭제하면,

[Head] -> [A] -> [B:Tail] -> [A]  이렇게 된다.

① [B].next.next = NULL    // next 가 Tail 인 녀석을 찾아보니 [B]. 즉, [B].next = Tail

연산 후 모습 : [Head] -> [A] -> [B] -> [C:Tail]

② free([B].next)

연산 후 모습 : [Head] -> [A] -> [B] -> [ ]

③ [B].next = [Head].next 

연산 후 모습 : [Head] -> [A] -> [B] -> [A]

④ *tail = [B]

[Head] -> [A] -> [B:Tail] -> [A]

3. Double Linked List

- previous, next 가 존재해서 조금 귀찮다.

- 어떤 책은 prev / next 로 하는 책도 있고, left /right 로 하는 책도 있는데 전자를 선택하겠다.

- 앞에 보았던 노드의 구조가 [Data, Next] 라면 지금은 [Prev, Data, Next] 정도 되겠다.

(1) Insert

- Header

[Head] ↔ [A] ↔ [B] ↔ [C:Tail]  이런 상태에서

[Head] ↔ [?] ↔ [A] ↔ [B] ↔ [C:Tail] 로 [?] 라는 노드를 삽입할 것이다.

① [?].prev = [Head] 

② [?].next = [Head].next

③ [Head].next = [?]

④ [?].next.prev = [?]

- Middle (Header 와 똑같다고 보면 된다)

[Head] ↔ [A] ↔ [B] ↔ [C:Tail]  이런 상태에서

[Head] ↔ [A] ↔ [?] ↔ [B] ↔ [C:Tail] 로 [?] 라는 노드를 삽입할 것이다.

① [?].prev = [A] 

② [?].next = [A].next

③ [A].next = [?]

④ [?].next.prev = [?]

- Tail

[Head] ↔ [A] ↔ [B] ↔ [C:Tail]  이런 상태에서

[Head] ↔ [A] ↔ [B] ↔ [C] ↔ [?:Tail] 로 [?] 라는 노드를 삽입할 것이다.

① [?].prev = [C:Tail] 

② [?].next = NULL

③ [C:Tail].next = [?]

④ *tail = [?]

(2) Remove

- Header

[Head] ↔ [A] ↔ [B] ↔ [C:Tail] 이런 상태에서 [A] 를 삭제하면,

[Head] ↔ [B] ↔ [C:Tail] 이렇게 된다.

① [Head].next = [A].next    또는    [Head].next = [Head].next.next

② [Head].next.prev = [Head]

③ [A].prev = NULL    // ①, ② 연산으로 [A]를 가르키는 노드가 없으니 ① 연산 전에 [A]를 따로 저장

④ [A].next = NULL

⑤ free([A])

- Middle (Header 와 똑같다고 보면 된다)

[Head] ↔ [A] ↔ [B] ↔ [C:Tail] 이런 상태에서 [B] 를 삭제하면,

[Head] ↔ [A] ↔ [C:Tail] 이렇게 된다.

① [A].next = [B].next    또는    [A].next = [A].next.next

② [A].next.prev = [A]

③ [B].prev = NULL    // ①, ② 연산으로 [B]를 가르키는 노드가 없으니 ① 연산 전에 [B]를 따로 저장

④ [B].next = NULL

⑤ free([B])

- Tail

[Head] ↔ [A] ↔ [B] ↔ [C:Tail] 이런 상태에서 [C] 를 삭제하면,

[Head] ↔ [A] ↔ [B:Tail] 이렇게 된다.

① [B].next.prev = NULL    // next 가 Tail 인 녀석을 찾아보니 [B]. 즉, [B].next = Tail

② free([B].next)

③ [B].next = NULL

④ *tail = [B]

# Linked List 사용 사례 : 

- Stack, Queue, Tree 구현할 때 사용될 수 있다.

- 많이 쓰이기는 하는데 막상 사용 예제를 검색해보면 딱히 나오지는 않는 것 같다...

아, 드럽게 많네.

그림 별로 안 올려도 포스팅 하는데 겁나 오래걸린다ㅠㅠ

( + 이 포스팅에서 free 나 *tail 은 C언어로 쓰인 자료 참고하느라 추가했다.

원래 Java 로 코드를 한번 짜봤었는데 C 로는 안 해봐서 조금 지저분해도 써봤다. )