연결 리스트 - 단일 연결 리스트

배열의 중간에 데이터를 삽입/삭제할 때의 시간복잡도는 $O(n)$ 이었습니다. 따라서 삽입과 삭제가 자주 발생하는 상황에서는 배열이 비효율적일 수 있는데요, 그럼 어떠한 자료구조를 사용해야 할까요? 오늘은 삽입과 삭제의 연산이 빠른 단일 연결 리스트에 대해 알아보도록 하겠습니다.

 

📦  노드

연결 리스트를 이해하기 위해서 알아야 하는 노드라는 개념이 있습니다. 쉽게 말해 데이터를 담고있는 박스라고 생각하면 됩니다. 연결 리스트들은 이 노드들이 여러개 모여 이루어진 구조인데요, 배열과 달리 한 노드에서 다른 노드로 이동하는 경로를 가지고 있습니다. 이것을 '다른 노드를 참조한다' 라고 합니다.

 

🚂  단일 연결 리스트

그러면 '단일' 연결 리스트는 무엇일까요? 이름에서 알 수 있듯, 단방향(한쪽 방향)으로 연결되어있는 연결 리스트를 단일 연결 리스트라고 부릅니다. 노드들은 각자 바로 다음 노드에 대한 참조를 가지고 있습니다.

위와 같이 각 노드별로 data라는 값과 next라는 값을 가지고 있는데요, data는 데이터 값을, next는 그 다음 노드의 위치를 표시합니다. 노드의 갯수에 따른 연결 리스트 모양을 다음과 같이 나타낼 수 있습니다.

 

 

노드가 단 1개밖에 없을 때는 다음 노드가 없기 때문에 next 값이 null이 됩니다.

 

 

노드가 2개일 때는 첫 번째 노드의 next 값이 Node2가 되며, Node2의 next값이 null이 됩니다.

 

🔷 head와 tail 노드

단일 연결 리스트를 탐색하려면 해당 리스트의 첫 번째 노드를 알아야 하는데요, 그 첫 번째 노드를 head라고 부릅니다. 또한, 마지막 노드는 tail이라고 합니다. 리스트를 만들 때는 항상 head와 tail을 지정해주어야합니다.

자바스크립트로 노드와 단일 연결 리스트를 구현하면 다음과 같습니다.

class Node() {
    constructor(data) {
    	this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor(data) {
    	this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

 

 

🧮 연산의 종류

🔎 탐색

단일 연결 리스트에서의 탐색은 Head 부터 Tail까지 하나씩 확인해야 합니다. 따라서 $O(n)$의 시간복잡도로 표현됩니다.

 

➕ 삽입

삽입을 할 때는 인접한 노드들의 연결을 끊고 그사이에 새로운 노드를 넣어줍니다. 연결 작업만 이루어지기 때문에 $O(1)$의 시간복잡도로 표현됩니다.

 

Node와 Tail 사이에 새로운 노드인 Node2를 넣는다고 가정해 봅시다.

Node의 next값을 Node2로, Node2의 next값은 Tail로 바꿔주어 중간에 삽입해줍니다. 이와 같은 과정을 자바스크립트 코드로 표현하게 되면 다음과 같습니다.

//node와 this.tail이 있다고 가정
const node2 = new Node(newData); //node2 생성
node.next = node2; //node의 next에 node2 연결
node2.next = this.tail; //node2의 next에 tail 연결

 

 

➖ 삭제

삭제하고 싶은 노드의 연결을 끊고, 앞뒤의 노드를 연결해주면 됩니다. 삭제 또한 연결 작업만 이루어지기 때문에 $O(1)$의 시간복잡도로 표현됩니다.

 

아까 삽입했던 Node2를 다시 삭제해 봅시다.

Node의 next를 Tail 노드로 바꾸어준 후, Node2의 next는 null로 만들어 연결을 끊어줍니다. 역시 자바스크립트로 구현하면 다음과 같습니다.

//node와 this.tail이 있다고 가정
node.next = this.tail; //node의 next에 tail 연결
node2.next = null; //node2의 next를 null로 변경

 

 

이처럼 단일 연결 리스트는 탐색에 $O(n)$의 시간복잡도를 가지고 있지만, 삽입과 삭제는 $O(1)$의 시간복잡도를 가집니다. 따라서 삽입과 삭제가 자주 일어나는 경우, 삽입/삭제의 시간복잡도가 $O(n)$인 배열보다 단일 연결 리스트를 쓰는 것이 효율적입니다.