[Data Structure] CHAP 6. Singly Linked Lists (단일 연결 리스트) - C언어 ver.

이번 챕터에서는 연결리스트에 관한 내용을 작성하려고 한다. 관련내용은 아래와 같은 순서로 정리할 예정이다.

• 연결리스트의 원리
• 단일 연결리스트의 특징
• 단일 연결리스트 생성코드
• 단일 연결리스트에서 노드 추가/제거
• 순환 연결리스트의 특징
• 순환 연결리스트에서 노드 추가/제거

그럼 시작 -!

---

0. Linked Lists

연결리스트란 노드들로 구성된 자료구조형태이며 노드는 두 칸으로 쓴다. 앞에는 데이터를 저장하고, 뒤 칸에는 다음 노드의 주소값을 저장해 멀리 있어도 찾아갈 수 있도록 한다. 첫 노드의 주소는 head라는 변수를 설정하여 저장하고, 마지막 노드는 주소값을 NULL값으로 가진다.

배열은 값이 연속으로 할당된다는 특징이 있어, 만약 내가 5칸의 메모리공간이 필요한데 2칸, 4칸의 공간이 각각 있다면 이용할 수 없다. 꼭 연속 5칸의 공간이 필요한 것이다. 하지만 연결리스트를 사용하면 각각의 데이터를 저장 후 연결만 해주면 되기 때문에 이용이 가능해진다.

 

연결 리스트의 종류에는 아래와 같이 세 가지가 있다.

각각의 연결리스트에 대한 설명을 하나씩 진행하려 한다.

---

1. Singly Linked Lists (단일연결리스트)

단일 연결리스트란 한 방향으로 연결되는 연결리스트를 말한다.

단일 연결리스트도 연결리스트의 일종이므로 한 노드당 두 칸을 갖는다. 그래서 배열과 단순 수치화 해서 비교하면 아래와 같이 쓸 수 있다.

...	Array	Linked List
			메모리양	n	2n

하지만 데이터와 주소는 메모리 차이가 있기 때문에 단순히 2배 차이가 난다고 할 수는 없으며, Big-O로 나타내면 둘 다 O(n)이기 때문에 'Array가 메모리를 덜 차지한다'라고 일반화 하기엔 무리가 있다.

1-1. 단일 연결리스트 생성코드

단일 연결리스트의 소스 코드를 작성하면 아래와 같이 쓸 수 있다.

listPointer create2() {
	listPointer first, second;
    MALLOC(first,sizeof(*first));		
    MALLOC(second,sizeof(*second));		//각각 first, second에 리스트 첫 부분 주소 넣음
    
    second -> link = NULL;
    second -> data = 20;
    first -> data = 10;
    first -> link = second;
    return first;
}

참고로 MALLOC은 메모리 공간을 동적할당 할 때 쓰는 함수이다.
위 코드에서 가장 포인트가 되는 부분은 first -> link = second 부분이다. 앞 노드에 뒤 노드의 주소를 넣어줘야한다!

 

1-2. 단일 연결리스트에 노드 추가

먼저 head부분에 노드를 추가하는 과정을 살펴보자.

1. malloc을 이용해 새 노드를 할당한 후 값을 넣어준다.
2. 새 노드에 기존 첫 노드의 주소를 넣어준다.
3. head에 새 노드의 주소를 넣어준다.

헤드 포인터를 마지막에 바꿔주는 것이 포인트이다. head포인터에 들어있던 기존 첫 노드의 주소를 통해 새 노드에 주소를 넣을 수 있는 건데 head포인터 주소를 먼저 바꾸면 기존 첫 노드의 주소를 알 방법이 없게 된다.

tail 뒤에 노드를 추가하는 과정도 마찬가지이다.

1. malloc을 통해 새 노드를 할당한 후 값을 넣어준다.
2. 새 노드의 포인터를 NULL값으로 지정한다.
3. 기존 마지막 노드에 새 노드 주소를 넣어준다.
4. tail에 새 노드의 주소를 넣어준다.

+) 단일연결리스트에 노드 추가시 worst case

단일 연결리스트에 노드를 추가할 때 worst case는 언제일까? 바로 tail 직전에 노드를 추가할 때이다. 이유는 아래 그림을 통해 설명하려고 한다

tail 직전에 노드를 추가하게 되면, 먼저 새 노드 u를 할당 후 마지막 노드의 주소를 넣어준다. 마지막 노드의 주소는 이미 변수 tail에 저장되어 있으므로 큰 어려움이 없을 것이다. 그런데 문제는 노드 t에 u의 주소를 저장할 때 생긴다. t에 u의 주소를 넣기 위해서는 t의 주소를 알아야 하고, 이를 알기 위해서는 앞으로 앞으로 가다가 결국 첫 노드까지 가야한다. 즉 n-1회를 반복해야 한다는 것이다.

그러므로 worst case는 tail 직전에 노드를 추가할 때이며, O(n)임을 알 수 있다.

 

1-3. 단일 연결리스트에 노드 제거

먼저 head 노드를 제거하는 과정을 살펴보려고 한다.

1. head포인터의 주소를 기존 head의 다음 노드로 옮겨준다.
2. 제거하려는 노드를 deallocation처리 해준다.

2번에 써있는 내용은 노드를 제거한 후에는 꼭 free()를 이용해 사용했던 빈 메모리를 다른 사람이 쓸 수 있도록 해줘야 한다는 의미이다.
참고로 head 노드를 제거할 때에는 O(1)로 표현할 수 있다!

이번엔 tail 노드를 제거하는 과정을 살펴보자.

1. tail포인터의 주소를 뒤에서 두번째 노드로 옮겨준다.
2. 뒤에서 두번째 노드의 포인터를 NULL값으로 지정한다.
3. 제거하려는 노드를 deallocation처리 해준다.

과정을 쓴다면 위와 같이 쓸 수 있지만 문제가 생긴다. 뒤에서 두번째 노드로 tail 포인터를 옮기려면 뒤에서 두번째 노드의 주소를 알아야 하는데 이를 알려면 결국 첫번째 노드로 이동해야 한다는 것이다. 그래서 이를 big-O로 표현하면 O(n)이 된다.

이런 과정을 개선하기 위해 생긴 것이 Circularly Linked List(순환 연결리스트)이다.

---

2. Circularly Linked List (순환 연결리스트)

먼저 Doubly Linked List(이중 연결리스트)는 앞뒤 노드가 서로 연결되는 순환리스트로, 단일연결리스트는 노드가 2칸이었지만 이중연결리스트는 앞 노드의 주소를 연결하는 공간이 추가되어 3칸으로 구성되어있다.

순환 연결리스트는 Doubly Linked List (이중 연결리스트)의 일종으로, 이중 연결리스트에서 처음과 끝이 연결되어 순환하는 모습을 하고있는 연결리스트이다.

2-1. 순환 연결리스트에 노드 추가/제거

단일 연결리스트에 노드 추가시 worst case였던 'tail직전의 추가'를 순환 연결리스트에서 해보면 tail직전의 노드 주소를 바로 알 수 있게 되므로 O(1)로 개선되었다는 것을 알 수 있다.

물론 한 가운데에 추가/ 제거를 하게 된다면 O(n)으로 worst case가 생기지만, average case를 살펴보게 된다면 n과 n/2는 차이가 있게 된다!.

---

참고 : https://devopedia.org/linked-list-data-structure

Linked List (Data Structure)