[자료구조] Singly Linked List

*** 개인이 공부한 내용들을 간략하게 정리하고 참고하기 위한 포스팅입니다. 설명에 실수가 있을 수 있습니다. 지적해 주시면 정말 감사하겠습니다. ***

Array의 단점

1. 고정된 길이를 가지고 있는 자료구조이기 때문에, 동적으로 resizing할 일이 생길 수 있다. 이 경우 새로운 array를 만들고 > element들을 복사하고 > 새로 생성한 array로 reference를 재설정해 줘야 하기 때문에 비효율적이다.

2. 앞 쪽 index에 새로운 값을 추가하려는 경우, 그 뒷쪽 값들을 전부 다 한 칸씩 밀어 줘야 하기 때문에 비효율적이다. 

예를 들어 1, 2, 3, 4, 5가 저장된 array가 있고 0th index에 6을 저장하려는 경우, {6,1,2,3,4,5}를 만들기 위해 1,2,3,4,5를 모두 뒤로 한 칸 씩 밀어야 할 것이다.

3. (원론적으로) array는 memory 내의 contiguous block으로 구현되므로, array concatenation 연산이 O(n+m) time의  initialization을 요구한다.

 

이러한 array의 단점을 보완하기 위해 고안된 자료구조가 Linked List이다. 배열의 크기는 compile time에 고정되는데 반해 Linked List는 자유로이 크기를 늘릴 수 있고, 같은 이유로 array에 할당된 memory보다 실제 저장된 data 수가 적어 memory 낭비가 발생하는 문제도 해결할 수 있다.
또한, 각 노드가 다른 노드를 지시하는 pointer를 가지고 있는 형태로 구현되기 때문에, 데이터를 삽입할 때 데이터를 일일이 shifting 할 필요가 없어진다.

 

오늘 포스팅에서는 가장 기본적인 형태인 Singly Linked List를, 다음 포스팅에서는 Doubly Linked List와 Circular Linked List를 다룬다.

 

Singly Linked List

Singly Linked List는 (data 값 + 다음 node로의 link)를 가지고 있는 node들로 구성된다. 

각 node들의 link는 다음 node를 지시하고 있고, 이 중 NULL을 지시하는 link를 가진 node가 해당 SLL의 마지막 node가 된다. 

가장 첫 번째 node를 지시하는 pointer를 head, 마지막 node를 지시하는 pointer를 tail이라고 한다. 

 

앞서 array와 비교했을 때 SLL의 장점을 소개하였지만, 이 구조에서 다시 SLL의 단점이 드러난다.

 

array의 경우, 각각의 element들이 모두 indexing 되어 있기 때문에 특정 element를 탐색하는 시간이 O(1)이다. index만 주어지면 바로 해당 element에 접근할 수 있기 때문이다.

그러나 Linked List의 경우 그렇지 않기 때문에, 원하는 원소가 나올 때까지 해당 List를 순회하여야 한다. 따라서 time complexity가 O(n)이 되므로 이 부분은 array에 비해 비효율적이다.

 

반면 insertion/removal 연산은 경우에 따라 다르게 접근해야 한다.

1. 맨 앞에 추가하는 경우(AddFirst 연산) : 새로운 node를 추가하고 그 node를 기존 head에 연결한 다음, 새로 추가된 node를 새로운 head로 삼으면 되기에 time complexity가 O(1)이다. array였다면 맨 앞에 element를 추가하기 위해 다른 element들을 전부 shifting 시켜야 하기에 이 경우 SLL이 더 효율적이다.

Function AddFirst(data):
	newest = Node(data)
    	newest.next = head
    	head = newest
    	size+=1

2. 맨 뒤에 추가하는 경우(AddLast 연산) : 기존 tail을 node를 찾아서 새로 추가된 node와 연결해 준 다음, 새로 추가된 node를 새로운 tail로 삼는다. 

여기서 포스팅을 하기에 헷갈리는 점을 발견했는데, 학교 수업에서 사용했던 교재와 필기, 구글링과 gpt(무려 유료 ㄷㄷ)를 통한 각종 검색에서 이 연산이 요구하는 time complexity를 조금씩 다르게 말했기 때문이다. 

구할 수 있는 자료와 내 지식을 종합해서 생각해 봤을 때, tail pointer를 사용하는 SLL의 경우 바로 tail에 접근할 수 있기 때문에 O(1)이 되고, tail pointer가 없는 경우 traversing이 필연적이기에 O(n)이 되는 것 같다. 학교에서 배웠을 때는 head/tail이 무조건 있는 모형으로 배웠는데, 구글 이미지 검색을 통해 여러 참조 이미지들을 찾아본 결과 tail pointer는 필수적으로 들어가지는 않았기 때문이다.

Function AddLast(data):
	newest = Node(data)
    	tail.next = newest
    	newest.next = null
        tail = newest
    	size+=1

3. 맨 앞에서 삭제(RemoveFirst 연산)

기존 head가 지시하는 node를 새 head로 삼기만 하면 된다. 

Function RemoveFirst():
	if(head==null) return
	head = head.next
    	size-=1

그럼 유기된 기존 head는 어떻게 처리되지? 하는 의문이 생겨서 찾아보았는데, Garbage Collector가 최종적으로 이들을 memory에서 제거한다고 한다. Garbage Collector에 대해서 아직 잘 모르는데 차후에 공부할 때 다시 확인해 봐야겠다.

 

4. 맨 뒤에서 삭제(RemoveLast 연산)

tail을 "지시하는" node를 찾아 해당 node를 null을 지시하는 tail로 재설정한다.

Function RemoveLast():
    node = head
    	while(node.next==tail):
        	node = node.next
            
        node.next = null
        tail = node

 

tail pointer가 있더라도 SLL은 "단방향으로"만 연결된 자료구조이므로 반드시 traversing이 요구된다. 따라서 time complexity는 O(n)이다.