[자료구조] Doubly Linked List의 삽입(중간노드, 첫번째 노드, 마지막노드로 삽입)

Doubly Linked List는 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트이다. linked list에서와 마찬가지로 중간노드, 첫번째 노드, 마지막 노드 삽입을 나누어서 보도록 하겠다.

 

https://imsunbow.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-List-%EC%82%BD%EC%9E%85%EC%A4%91%EA%B0%84-%EB%85%B8%EB%93%9C-%EC%B2%AB%EB%B2%88%EC%A7%B8-%EB%85%B8%EB%93%9C%EB%A7%88%EC%A7%80%EB%A7%89-%EB%85%B8%EB%93%9C%EB%A1%9C-%EC%82%BD%EC%9E%85

 

[같이 보면 좋은 자료: linked list에서의 삽입]

 

 

1) 중간 노드로 삽입

 

- 삽입할 노드를 먼저 준비한다.

- 새 노드의 데이터 필드에 값을 저장한다.

- 새 노드 왼쪽 노드(pre)의 rlink 필드에 있던 값을 새 노드의 rlink 필드에 저장한다.

- 왼쪽 노드의 rlink 필드에 새 노드의 주소를 저장한다.

- 새 노드의 llink 필드에 왼쪽 노드(pre)의 주소를 저장한다.

- 오른쪽 노드의 llink 필드에 새 노드의 주소를 저장한다.

 

2) 첫 번째 노드로 삽입

 

- 삽입할 노드를 먼저 준비한다.

- 새 노드의 데이터 필드에 값을 저장한다.

- 새 노드의 왼쪽 노드가 없으므로 새 노드의 llink 필드에 NULL을 저장한다.

- head가 가리키고 있던 첫 번째 노드의 주소값을 새 노드의 rlink 필드에 저장한다.

- 첫 번째 노드였던 노드의 llink 필드에 새 노드의 주소값을 저장한다.

- head에 새 노드를 연결한다.

 

3) 마지막 노드로 삽입

 

- 삽입할 노드를 준비한다.

- 새 노드의 데이터 필드에 값을 저장

- 새 노드의 오른쪽 노드가 없으므로 새 노드의 rlink 필드에 NULL을 저장한다.

- 마지막 노드를 검색한다.

- 새 노드의 llink 필드에 마지막 노드의 주소값을 저장한다.

- 마지막 노드의 rlink 필드에 새 노드의 주소값을 저장한다.