연결 리스트 (Linked List)의 연산

Linked List(연결 리스트)는 배열(Array)과 같이 순차적인 데이터를 표현하는 데 적합한 자료 구조이다. 각 데이터 항목을 node(노드)라고 부르며, 이 node들이 포인터로 연결되어 리스트를 구성한다.

Node(노드): 데이터와 다음 node를 가리키는 포인터(link 또는 next)로 구성된 단위이다. item(항목) 또는 element(원소)라고도 부른다.
Head(헤드): Linked List의 첫 번째 node를 가리키는 포인터이다.
장점: 프로그램 실행 중에 메모리가 허용하는 한 동적으로 node의 수를 늘리거나 줄일 수 있다. 이는 자기 참조 구조체(self-referential structure)를 이용하여 구현된다.

Node(노드) 추가

Linked List의 가장 앞에 새로운 node를 추가하는 과정은 다음과 같다.

이 방식을 사용하면 리스트의 길이에 상관없이 항상 빠른 시간 안에 node를 추가할 수 있다.

Linked List의 가장 마지막에 새로운 node를 추가하는 과정은 다음과 같다.

Linked List의 중간에 새로운 node를 삽입하는 과정은 다음과 같다.

데이터가 정렬된 상태를 유지하도록 Linked List에 node를 삽입하는 경우, 삽입 위치를 찾아야 한다. 이 과정은 주로 두 개의 포인터(p, q)를 사용하여 효율적으로 처리할 수 있다.

삽입 과정:

p와 q를 head(헤드)에서부터 이동시키며 새로운 데이터가 들어갈 위치를 탐색한다. p의 데이터가 삽입할 데이터보다 커지는 순간이 삽입 위치이다.
탐색이 완료되면 새로운 node를 q와 p 사이에 삽입한다.
- newNode->next = p;
- q->next = newNode;
예외 처리:
- 맨 앞에 삽입: 삽입할 데이터가 head의 데이터보다 작을 경우, head를 새로운 node로 갱신해야 한다.
- 맨 뒤에 삽입: 리스트의 끝까지 탐색한 경우(p가 NULL이 된 경우), 마지막 node(q) 뒤에 새로운 node를 추가한다.

Linked List에서 특정 node를 삭제하는 과정은 다음과 같다.

정렬된 Linked List에서 node를 삭제하는 과정은 삽입과 마찬가지로 두 개의 포인터(p, q)를 사용한다.

삭제 과정:

p와 q를 이동시키며 삭제할 데이터를 가진 node(p)를 찾는다.
최적화: 탐색 중 p의 데이터가 삭제할 데이터보다 커지면, 해당 데이터는 리스트에 존재하지 않는 것이므로 탐색을 즉시 중단할 수 있다.
삭제할 node를 찾으면, q의 link가 p의 다음 node를 가리키도록 변경한다.
- q->next = p->next;
p가 가리키는 node의 메모리를 해제한다.
예외 처리:
- 맨 앞 Node(노드) 삭제: 삭제할 node가 head(헤드)일 경우, head를 다음 node로 갱신한 후 기존 head의 메모리를 해제해야 한다.
- 삭제할 Node(노드)가 없는 경우: 리스트의 끝까지 탐색해도 데이터를 찾지 못하면 아무 작업도 수행하지 않는다.