[JS] Singly Linked List 구현 (단일 연결 리스트)
Singly Linked List는 head, tail 참조를 갖는 구조로 만든다.
마지막 요소 (tail)를 참조하는 포인터를 가지고 있어야 마지막 요소에 값을 추가하는 시간복잡도가 O(n)이 아니라 O(1)로 만들 수 있다.
구현할 메서드
- addFirst(e) - 연결 리스트 맨 앞에 요소 추가
- addLast(e) - 연결 리스트 맨 마지막에 요소 추가
- add(index, e) - 특정 위치에 요소를 추가
- get(index) - 특정 위치에 요소를 반환
- set(index, e) - 특정 위치에 요소를 parameter로 전달된 요소로 변환
- remove(index) - 특정 위치에 요소를 삭제
노드 생성자
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}연결리스트는 노드로 구성되어 있기 때문에 가장 먼저 노드 객체를 생성하는 생성자를 만들어주어야 한다.
해당 노드 생성자는 노드가 가지는 데이터를 초기화하고, 다음 노드를 가리키는 값을 null 로 초기 설정하는 역할을 한다.
add()
현재 포스팅 목적에 맞는 add() 메서드를 구현하기 위해서는 해당 메서드가 두 개로 나뉘어야 한다.
하나는 맨 앞에 추가되는 메서드와 다른 하나는 맨 끝에 추가되는 메서드이다.
우선은 가장 기본적으로 tail 포인터가 없는 가장 기본적으로 동작하는 add() 메서드를 구현해 보았다.
class LinkedList {
constructor() {
this.head = null;
}
add(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode; // 연결 리스트가 비어있을 경우 head가 새로 추가된 노드를 가리키도록 설정
} else {
let current = this.head; // 현재 head인 노드
while (current.next) {
// next값이 null인 가장 끝(오른쪽) 노드가 될 때 까지 loop을 돌며 현재 노드를 마지막 노드로 초기화
current = current.next;
}
current.next = newNode; // 마지막 노드의 next가 새로 추가한 노드를 가리키도록 설정
}
}
}- 연결리스트 생성자를 만들어 준다.
- head 를 null로 초기화 한다.
- add() 메서드 안에서 인자값을 통해 새로운 노드 객체를 생성한다.
- 첫 노드를 추가하는 작업인 경우에는 head 가 해당 노드를 가리키도록 한다.
- 그 이후 부터는 현재 head 가 가리키는 노드가 가리키는 다음 노드가 null 이 될 때 까지, while 문을 돌며 노드의 next 값을 초기화 한다.
- 마지막으로 새로운 노드를 현재 노드의 다음을 가리키도록 설정한다.
연결 리스트 생성자
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}addFirst()
addFirst(data) {
const newNode = new Node(data);
if (!this.head) {
// 연결 리스트가 비어있을 경우 head, tail 각각 새로 추가된 노드를 가리키도록 설정
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head; // 현재 head가 가리키는 노드를 새로 추가된 노드의 next로 초기화
this.head = newNode; // 새로 추가된 노드로 head를 초기화
}
this.length++; // 전체 길이 증가
}여기서는 새로운 노드가 맨 앞에 추가되어야 하기 때문에
새로 추가된 노드의 next 값을 기존의 head 값으로 초기화 해주고,
기존의 head 값을 새로운 노드로 초기화 해주어야 한다.
addLast()
addLast(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode; // 현재 tail이 가리키는 노드의 next 값을 새로 추가된 노드로 초기화
this.tail = newNode; // 새로 추가된 노드로 tail을 초기화
}
this.length++;
}새로운 노드가 맨 끝에 추가되려면,
tail과 tail 이 가리키는 next 값을 새로 추가된 노드를 가리키도록 만들면 된다.
add()
add(index, data) {
if (index === 0) {
this.addFirst(data);
} else if (index === this.length) {
this.addLast(data);
} else {
const newNode = new Node(data);
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next; // current를 index - 1 위치에 존재하는 노드로 설정 (우리가 넣고자 하는 인덱스의 직전 노드)
}
newNode.next = current.next; // 새로 추가된 노드가 현재 노드의 다음 노드를 가리키도록 초기화
current.next = newNode; // 현재 노드가 새로 추가된 노드를 가리키도록 초기화
this.length++;
}
}원하는 인덱스에 data 를 삽입하는 경우에는 현재 노드를 삽입 위치 직전의 노드로 설정하고,
현재 노드의 next 값을 새로 추가된 노드로,
새로 추가된 노드의 next 값을 현재 노드의 next 로 초기화 시켜주어야 한다.
get()
get(index) {
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next; // current를 index 위치에 존재하는 노드로 설정 (우리가 찾고자 하는 인덱스의 노드)
}
return current.data;
}원하는 값을 찾을 때는 위의 add() 메서드에서 for 문만 살짝 수정해주면 쉽게 구현이 가능하다.
set()
set(index, data) {
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
current.data = data;
}마찬가지로 원하는 인덱스에 위치한 data를 바꾸는 작업는 get() 메서드와 유사하다.
get() 이 찾기 였다면,
set() 은 찾고, 초기화다.
remove()
remove(index) {
if (index === 0) {
this.head = this.head.next;
if (!this.head) {
this.tail = null;
}
} else {
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next; // current를 index - 1 위치에 존재하는 노드로 설정 (우리가 삭제하고자 하는 인덱스의 직전 노드)
}
current.next = current.next.next; // 삭제할 노드의 전 노드가 삭제할 노드의 다음 노드를 가리키도록 초기화
if (!current.next) {
this.tail = current; // 해당 값이 null일때, tail이 해당 노드를 가리키도록 초기화
}
}
this.length--;
}add() 메서드와 동일한 방식으로 원하는 인덱스 직전 노드를 찾은 다음,
삭제할 노드의 직전 노드가 삭제할 노드를 건너 띄고 그 다음 노드를 가리키도록 초기화해준다.
이때, 그 다음 노드가 존재하지 않아 null이 할당 될 경우 해당 노드가 마지막 노드가 되므로 tail이 해당 노드를 가리키도록 초기화 시켜준다.
전체 코드
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
addFirst(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
}
addLast(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
}
add(index, data) {
if (index === 0) {
this.addFirst(data);
} else if (index === this.length) {
this.addLast(data);
} else {
const newNode = new Node(data);
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
this.length++;
}
}
get(index) {
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
set(index, data) {
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
current.data = data;
}
remove(index) {
if (index === 0) {
this.head = this.head.next;
if (!this.head) {
this.tail = null;
}
} else {
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
if (!current.next) {
this.tail = current;
}
}
this.length--;
}
}마무리
연결 리스트는 삽입 및 삭제 연산에서 배열 보다 훨신 빠른 시간 복잡도로 연산을 수행할 수 있다.
가장 기본이라고 생각되는 자료구조이기 때문에 꼭 알고 넘어가야한다고 생각한다.
추가적으로 이중 연결 리스트, 원형 연결 리스트가 있다.
이중 연결 리스트는 주로 역순 및 양방향 탐색이 필요한 경우나 데이터의 삽입 및 삭제가 빈번한 경우에 사용하고,
원형 연결 리스트는 순환적인 작업이 필요한 상황에서 사용한다고 한다.