[자료구조]1. 단일 링크드 리스트, 단일 연결 리스트

자료구조란 쉽게 말해, 데이터를 저장하고 사용하기 위해 만드는 것이다.

세 가지 기본기능으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다.

자료구조는 구현방법과 성능분석이 중요하다.

 

링크드 리스트의 예시

링크드 리스트의 특징 (배열과 비교)

• 배열은 주소가 연속적이지만, 링크드 리스트는 주소가 연속적이지 않다.
• 배열은 크기가 고정이므로 공간이 부족하거나 낭비될 수 있지만, 링크드 리스트는 크기가 가변적이므로 부족, 낭비가 없다.
• 배열에 비해 접근이 느리고 구현도 어렵다.

 

단일 링크드 리스트

Node의 예시. 값을 담은 elem과 다음 node를 가리키는 포인터로 구성되어 있다.

단일 링크드 리스트의 모습. 단방향으로만 이루어져 있다.

• 단일 링크드 리스트는 node가 순차적으로 이루어져 있다.
• 각 노드는 값을 나타내는 element 부분과 다음 node를 가리키는 주소(포인터)로 구성된다.
• 맨 앞 노드를 Head라고 가리키고 맨 뒤 노드를 Tail이라고 한다.

 

헤드에 삽입(Insert)하기

1. 새로운 노드를 할당한다.
2. element, 값을 노드에 삽입한다.
3. 원래 head였던 node의 주소를 노드에 삽입한다.
4. head가 새로 만들어진 노드를 가리키도록 한다.

-> ∴ O(1) Time이 소요된다.

 

 

헤드에서 삭제(Delete)하기

1. head가 현재 head의 다음 노드를 가리키도록 한다.
2. garbage Collector가 노드를 수거하도록 한다. 

2번의 예시 코드는 

node* tmp;

tmp = this->head;

this->head = head->next;

free(tmp); // delete tmp;

-> ∴ O(1) Time이 소요된다.

 

 

테일에 삽입(Insert)하기

1. 새로운 노드를 할당한다.
2. element, 값을 노드에 삽입한다.
3. 노드가 null을 가리키도록 한다.
4. 원래 tail인 노드가 새 노드를 가리키도록 한다.
5. tail이 새 노드를 가리키도록 한다.

-> ∴ O(1) Time이 소요된다. (처음부터 tail까지 갈 필요 없이, tail에 이미 마지막 노드를 저장해 두었기 때문이다.)

 

 

테일에서 삭제(Delete)하기

1. 단일 링크드 리스트에서는 바로 이전 노드의 주소를 알아내기가 어렵다. (주소가 배열과 달리 연속적이지 않기 때문이다.)
2. 반복문을 사용해서 head에서부터 찾으면 가능하다. 이를 이용해서 tail 바로 이전의 node를 찾아서 삭제를 진행하면 된다. 이 경우, 시간낭비가 심해진다.

-> ∴ O(n) Time이 소요된다. 

 

 

링크드 리스트에서의 탐색

head에서부터 찾아야 하므로 O(n) Time이 소요된다.