[자료구조 with JS] 단일 연결 리스트 (singly linked list)
연결 리스트란 자바스크립트 내장 array처럼 문자열, 숫자 등 원하는 데이터를 저장하는 자료구조이다.
array와의 차이점은 인덱스 유/무이다.
연결 리스트는 인덱스가 없어 array처럼 인덱스를 통해 값에 접근할 수 없다.
연결 리스트는 다수의 노드들로 구성되고, 각 노드는 하나의 데이터 엘리먼트를 저장하는데 각 노드들은 next 포인터를 통해 연결되어 있다. 즉, 각 노드들은 next 포인터를 통해 다음 노드의 정보를 저장하고 있다. (다음 노드가 없다면 null 저장)
연결 리스트에서 중요한 것은 head, tail, length이다.
head는 연결 리스트의 시작 노드,
tail은 연결 리스트의 마지막 노드,
length는 연결 리스트의 길이이다.
head 노드가 어디 있는지 알면, 그 노드로 다음 노드를 알아내는 방식으로 진행해서 tail 노드까지 접근 가능하다.
단일 연결 리스트는 각 노드가 다음 노드로 오직 단일 방향으로만 연결된 연결 리스트이다.
각 노드는 value라고 불리는 단일 데이터 항목과 다음 노드에 대한 참조 정보인 next를 저장하고 있다.
아래 코드는 노드와 단일 연결 리스트의 기본 구조이다.
class Node {
constructor(val) {
this.val = val;
this.next = null; // 처음에는 아직 다음 노드가 없기 때문에 null로 초기화
}
}
class SinglyLinkedList {
constructor() {
// head, tail 포인터와 length 초기화
this.head = null;
this.tail = null;
this.length = 0;
}
}push 메서드는 연결 리스트 맨 마지막에 인자로 받은 값을 추가한다.
push(val) {
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}head가 null이면 처음 삽입한 값이므로 head와 tail에 newNode를 할당하고,
값이 존재한다면 tail.next와 tail에 newNode를 할당한다.
***
this.tail.next에 먼저 할당하는 이유는
현재 this.tail은 원래 연결 리스트에 마지막 요소이므로 해당 요소의 next 포인터에 newNode를 할당해 주고,
그다음 this.tail에 newNode를 할당해서 마지막 요소로 만들기 위함이다.
***
// new 키워드를 사용해 SingltLinkedList의 새로운 인스턴스 생성 후 push
let list = new SinglyLinkedList();
list.push("Hi");
list.push("Hello");
처음 생성했을 땐 head, tail이 모두 null이고 length가 0이다.
push를 통해 값을 추가하면 head와 tail, length가 잘 변하는 것을 볼 수 있다.
pop 메서드는 연결 리스트의 마지막 노드를 제거 후 반환한다.
단순히 마지막 노드를 꺼내오는 것이 아니라,
처음부터 시작해서 마지막 노드 전 노드를 tail로 설정 후 next 포인터에 null을 할당한다.
pop() {
if (!this.head) return undefined;
let current = this.head;
let newTail = current;
while (current.next) {
// newTail은 항상 current가 이전에 가리키던 것으로 설정
newTail = current;
current = current.next;
}
this.tail = newTail;
this.tail.next = null; // 새로 설정된 tail의 next를 null로 설정함으로써 마지막 값이라는 걸 알려줌
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}let list = new SinglyLinkedList();
list.push("Hi");
list.push("Hello");
list.push("!");
list.pop(); -> !
list.pop(); -> Hello
list.pop(); -> Ho
list.pop(); -> undefined
list
shift 메서드는 연결 리스트 맨 앞 노드를 제거 후 반환한다.
(head가 그 다음 노드를 가리키게 함)
shift() {
if (!this.head) return undefined;
let currentHead = this.head;
this.head = currentHead.next;
this.length--;
if (this.length === 0) {
this.tail = null;
}
return currentHead;
}let list = new SinglyLinkedList();
list.push("Hi");
list.push("Hello");
list.push("!");
list.shift(); -> !
list.shift(); -> Hello
list.shift(); -> Ho
list.shift(); -> undefined
list
unshift 메서드는 연결 리스트의 맨 앞에 요소를 추가한다.
(headr가 입력 값을 가리키게 함)
unshift(val) {
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
}
else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}let list = new SinglyLinkedList();
list.push("Hi");
list.push("Hello");
list.push("!");
list.unshift("hahaha");
연결 리스트의 head가 hahaha이고, next 포인터가 Hi를 가리키며 길이가 4로 늘어난 것을 볼 수 있다.
get 메서드는 입력받은 인덱스 값에 위치하는 노드를 반환한다.
get(idx) {
if (idx < 0 || idx >= this.length) return null;
let counter = 0;
let current = this.head;
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}let list = new SinglyLinkedList();
list.push("Hi");
list.push("Hello");
list.push("!");
list.get(1);
set 메서드는 입력받은 인덱스 값에 위치하는 노드를 입력받은 값으로 업데이트한다.
원하는 위치 값 변경 후 true를, 노드 찾지 못했을 경우 false를 반환한다.
set(idx, val) {
let foundNode = this.get(idx);
if (foundNode) {
foundNode.val = val;
return true;
}
return false;
}let list = new SinglyLinkedList();
list.push("Hi");
list.push("Hello");
list.push("!");
list.set(1, "HaHaHa");
list
원래라면 head의 next가 가리키는 값이 Hello여야 되는데,
HaHaHa로 업데이트된 것을 볼 수 있다.
insert 메서드는 입력받은 인덱스 위치에 입력받은 값을 삽입한다.
set이 해당 인덱스 값을 변경하는 거라면, insert는 해당 인덱스에 값을 삽입하는 것이다.
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === this.length) {
this.push(val);
return true;
}
if (idx === 0) {
this.unshift(val);
return true;
}
// get 메서드로 idx-1에 위치한 노드 찾기
let newNode = new Node(val);
let prev = this.get(idx - 1);
let tmp = prev.next;
prev.next = newNode;
newNode.next = tmp;
this.length++;
return true;
}let list = new SinglyLinkedList();
list.push("Hi");
list.push("Hello");
list.push("!");
list.insert(1, "HaHaHa");
list
원래라면 head의 next가 가리키는 값이 Hello여야 되는데,
HaHaHa로 업데이트된 것을 볼 수 있다.
set 실행 결과와 다른 점은 연결 리스트의 길이이다.
위 set 실행 결과는 값의 삽입이 아닌 변경이라 길이는 그대로이지만,
insert는 값을 삽입한 거라 길이가 증가한다.
remove 메서드는 해당 인덱스에 위치한 값 삭제 후 그 값을 반환한다.
remove(idx) {
if (idx < 0 || idx === this.length) return undefined;
if (idx === 0) return this.shift();
if (idx === this.length) return this.pop();
let prev = this.get(idx - 1)
let removed = prev.next;
prev.next = removed.next;
this.length--;
return removed;
}위에서 정의한 get 메서드를 사용해 삭제하려는 인덱스보다 하나 앞에 있는 노드 정보를 얻어온다.
그 노드의 next가 가리키는 값이 삭제하려는 값이므로 두 노드를 변수에 넣고,
삭제하려는 값의 next 정보를 하나 앞에 있는 노드의 next 정보에 할당하면서
삭제하려는 노드와의 연결을 끊는다.
let list = new SinglyLinkedList();
list.push("Hi");
list.push("Hello");
list.push("!");
list.remove(1);
list
reverse 메서드는 노드 순서가 역으로 연결되도록 하여 연결 리스트를 뒤집는다.
리스트를 따라가면서 순서를 계속 역으로 바꿔나가야 한다.
reverse() {
// head와 tail 교환
let node = this.head;
this.head = this.tail;
this.tail = node;
let next;
let prev = null;
for (let i = 0; i < this.length; i++) {
next = node.next;
node.next = prev;
prev = node;
node = next;
}
return this;
}let list = new SinglyLinkedList();
list.push("Hi");
list.push("Hello");
list.push("!");
list.reverse();