정의
단일 연결 리스트는 선형 자료구조로,
각 데이터는 value(값), next(포인터)를 가진 Node라는 객체로 이루어져있다.
자료구조란, 데이터와 데이터 간의 관계 및 작업, 기능 등을 포함한 것을 의미한다.
단일 연결리스트는 head, tail, length 값을 가지고 있는 객체이다.
head는 단일 연결 리스트의 시작 Node를 의미하고,
tail은 마지막 Node를 의미한다.
length는 단일 연결리스트의 길이를 의미한다.
코드 및 구현
1. Node 객체 구현
ES2015 문법 중 class를 사용하여 구현해보자.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
Node 클래스는 new 연산자로 호출 시
value(값), next(포인터)를 가진 객체를 생성할 수 있다.
2. SingleLinked List 구현
단일 연결 리스트 head, tail, length 값을 가진 선형 자료구조이다.
head, tail에는 Node 객체가 할당되어 next(포인터)로 연결된다.
2.1. push 메서드 구현
단일 연결 리스트의 마지막 부분에서 요소를 추가하는 메서드
push(val) {
let node = new Node(val);
if (!this.head) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
this.length++;
return this;
}
만약 head가 null이라면, head와 tail에 node를 할당한다.
null이 아니라면, tail 다음에 node를 할당하고 tail에 node를 할당하여 tail 위치를 바꾼다.
head와 tail에는 Node 객체의 참조값이 저장되는 것이라는 것에 유념하면서 구현하자 ❗️
2.2. pop 메서드 구현
단일 연결 리스트의 마지막 요소를 제거하는 메서드
pop() {
if (!this.head) return;
let curr = this.head;
let prev = null;
while (curr.next) {
prev = curr;
curr = curr.next;
}
if (!prev) {
this.head = null;
this.tail = null;
} else {
prev.next = null;
this.tail = prev;
}
this.length--;
return curr;
}
head가 없으면 즉, 길이가 0이면 pop할 요소가 없으므로 undefined를 반환한다.
시작점은 head로 두고 다음 요소가 있을 때마다 시작점과 이전값을 수정한다.
다음 요소가 없으면 그 때의 시작점을 반환하고 tail, length 값을 수정한다.
2.3. shift 메서드 구현
단일 연결 리스트의 첫번째 요소를 제거하는 메서드
shift() {
if (!this.head) return;
let curr = this.head;
this.head = curr.next;
curr.next = null; // shifted된 요소 next 초기화
this.length--;
if (!this.length) {
this.tail = null
}
return curr;
}
head를 변수에 담고 head에 다음값을 head에 할당한다.
length를 수정하고 만약 length가 0이되면 tail 값도 수정해준다.
shifted 된 요소의 next 파라미터로 단일 연결 리스트에 접근할 수 있으므로 초기화 해준다.
2.4. unshift 메서드 구현
단일 연결 리스트의 첫번째 부분에 요소를 추가하는 메서드
unshift(val) {
let node = new Node(val);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head = node;
}
this.length++;
return this;
}
head가 없을 때는 push 메서드와 비슷하다.
하지만 head가 있으면 node의 다음을 현재 head에 할당된 node 객체를 할당하고
head에 node를 할당한다. 이에 따라 length도 증가시킨다.
2.5. get 메서드 구현
단일 연결 리스트의 인덱스에 해당하는 node 객체를 반환하는 메서드
get(index) {
if (index < 0 || index >= this.length) return null;
let curr = this.head;
for (let i = 0; i < index; i++) {
curr = curr.next;
}
return curr;
}
인덱스가 0보다 작거나 연결 리스트 길이보다 큰 값을 전달하면 null을 반환한다.
head에서부터 인덱스만큼 next로 이동하여 도달한 node 객체를 반환한다.
2.6. set 메서드 구현
단일 연결 리스트의 인덱스에 해당하는 node 객체의 val을 수정하는 메서드
set(val, index) {
let node = this.get(index);
if (!node) return false;
node.val = val;
return true;
}
앞서 구현한 get 메서드로 인덱스에 해당하는 node 객체를 조회한 후
node 객체의 val 프로퍼티에 접근하여 val 값을 수정한다.
2.7. insert 메서드 구현
단일 연결 리스트의 인덱스에 해당하는 위치에 node 객체를 추가하는 메서드
insert(val, index) {
if (index < 0 || index > this.length) return false;
if (index === 0) return !!this.unshift(val);
if (index === this.length) return !!this.push(val);
let node = new Node(val);
let prev = this.get(index - 1);
node.next = prev.next
prev.next = node;
this.length++;
return true;
}
인덱스가 0 보다 작거나 연결 리스트 길이보다 크면 실행되지 않는다.
인덱스가 0이면 unshift 로직과 동일하고, 인덱스가 연결 리스트 길이와 같으면 push 로직과 동일하다.
!!를 붙인 이유는 insert 메서드가 반환값으로 불리언을 반환해야하기 때문이다. ex) !!{} => true, !! null => false
2.8. remove 메서드 구현
단일 연결 리스트의 인덱스에 해당하는 node 객체를 제거하는 메서드
remove(index) {
if (index < 0 || index >= this.length) return;
if (index === 0) return this.shift();
if (index === this.length - 1) return this.pop();
let prev = this.get(index - 1);
let removed = prev.next
prev.next = removed.next;
removed.next = null; // removed 요소 next 초기화
this.length--;
return removed;
}
인덱스가 0보다 작거나 연결 리스트 길이보다 크거나 같으면
제거할 node를 선택할 수 없으니 undefined를 반환한다.
인덱스가 0이면 shift 로직, 연결 리스트 길이보다 1 작으면 pop 로직을 사용한다.
중간에 인덱스라면 get 메서드로 인덱스 이전 prev 값을 가져와서
prev 다음요소에 removed 다음 요소를 연결시킨 후 removed를 반환한다. 당연히 길이도 1 빼준다.
removed 된 요소의 next 값으로 단일 연결 리스트에 접근할 수 있으므로 null로 초기화 한다.
2.9. reverse 메서드 구현
단일 연결 리스트를 역순으로 재배치하는 메서드
reverse() {
if (this.length <= 1) return;
// swap
let temp = this.head;
this.head = this.tail;
this.tail = temp;
let prev = this.tail;
let curr = prev.next;
let next = curr.next;
while (next) {
curr.next = prev;
prev = curr;
curr = next;
next = curr.next;
}
curr.next = prev;
this.tail.next = null;
}
우선 head와 tail을 swap(교환)한다.
prev, curr, next 변수에 tail, tail.next, tail.next.next를 할당한다.
next 변수가 존재할 때까지 curr의 다음 요소를 prev로 수정하고
prev, curr, next 변수를 이동시킨다.
next 요소 null 이 되어 반복문이 종료되면,
현재의 curr.next가 아직 prev를 가리키지 않으므로
curr.next = prev을 작성해주고, tail의 다음 요소는 null로 수정한다.
tail이 되기 전에 1번 node는 head 였고 next 값이 2 node를 가리키고 있었으므로 tail의 next를 null로 수정해줘야한다.
완성 코드
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
// 연결리스트 마지막에 node 추가
push(val) {
let node = new Node(val);
if (!this.head) {
this.head = node;
} else {
this.tail.next = node; // tail의 할당된 객체의 참조값을 참조한다.
}
this.tail = node;
this.length++;
return this;
}
// 연결리스트 마지막에 node 제거
pop() {
if (!this.head) return;
let curr = this.head;
let prev = null;
while (curr.next) {
prev = curr
curr = curr.next
}
if (!prev) { // 연결리스트 길이가 1이어서, prev 값이 null
this.head = null;
this.tail = null;
} else {
prev.next = null;
this.tail = prev;
}
this.length--;
return curr;
}
// 연결리스트 시작에 node 제거
shift() {
if (!this.head) return;
let curr = this.head;
this.head = curr.next;
this.length--;
if (!this.length) {
this.tail = null;
}
return curr;
}
// 연결리스트 시작에 node 추가
unshift(val) {
let node = new Node(val);
if (!this.head) {
this.head = node;
this.tail = this.head;
} else {
node.next = this.head;
this.head = node;
}
this.length++;
return this;
}
// 인덱스로 node 참조
get(index) {
if (index < 0 || index >= this.length) return null;
let curr = this.head;
for (let i = 0; i < index; i++) {
curr = curr.next
}
return curr;
}
// 인덱스에 위치한 node 값을 수정
set(val, index) {
let node = this.get(index);
if (!node) return false;
node.val = val;
return true;
}
// 인덱스에 위치한 곳에 node 추가
insert(val,index) {
if (index < 0 || index > this.length) return false;
if (index === this.length) return !!this.push(val);
if (index === 0) return !!this.unshift(val);
let node = new Node(val);
let prev = this.get(index - 1);
node.next = prev.next;
prev.next = node;
this.length++;
return true;
}
// 인덱스에 위치한 node 제거
remove(index) {
if (index < 0 || index >= this.length) return;
if (index === this.length - 1) return this.pop();
if (index === 0) return this.shift();
let prev = this.get(index - 1);
let removed = prev.next;
prev.next = removed.next;
this.length--;
return removed;
}
// head, tail 역순
reverse() {
if (this.length <= 1) return;
// swap
let temp = this.head;
this.head = this.tail;
this.tail = temp;
let prev = this.tail;
let curr = prev.next;
let next = curr.next;
while (next) {
curr.next = prev;
prev = curr;
curr = next;
next = curr.next;
}
curr.next = prev;
this.tail.next = null;
}
// 출력
print() {
let arr = [];
let curr = this.head;
while (curr) {
arr.push(curr.val);
curr = curr.next;
}
console.log(arr)
}
}
연결 리스트 구조를 확인하기 위해 print 메서드를 추가했다.
시간 복잡도
단일 연결 리스트의 특징은 인덱스가 없어 랜덤 참조에 O(n) 시간 복잡도가 소요된다.
인덱스가 없어 맨 앞 요소에 데이터를 추가하더라도 시간 복잡도가 O(1)로 가장 우수하다.
단, 모든 삽입(insertion)에서 시간 복잡도가 O(1)인 것은 아니다.
중간이나 최악의 경우 맨 마지막 이전에 삽입하게 되는 경우 시간 복잡도가 O(n)이 될 수 있다.
배열과 비교했을 때, 상대적으로 맨앞에 요소가 추가되는 상황이 많다면 단일 연결 리스트를 고려해보는 것이 좋다.
단일 연결 리스트는 stack, queue 자료구조의 기반이 되므로 알아두어야 이후에 학습에도 도움이 될 것 이다.
참조
'Algorithm' 카테고리의 다른 글
| [Udemy] 스택(Stack)이란 ? (0) | 2024.08.02 |
|---|---|
| [Udemy] 이중 연결 리스트 (Double Linked List) 구현 (0) | 2024.08.01 |
| [Udemy] 지수 정렬(Radix sort)이란? (0) | 2024.07.30 |
| [Udemy] 퀵 정렬(Quick Sort)이란? (0) | 2024.07.29 |
| [Udemy] 병합 정렬(Merge Sort)이란? (0) | 2024.07.26 |
