📌 참고 사이트
자바스크립트로 연결 리스트를 구현하는 방법 (freecodecamp.org)
자바스크립트로 연결 리스트를 구현하는 방법
여러분이 만약 데이터 구조를 공부하고 있다면, 연결 리스트(linked list)는 반드시 알아야 할 구조 중 하나입니다. 연결 리스트를 좀 더 이해하고 싶거나 구현하는 방법이 궁금하다면 이 게시글이
www.freecodecamp.org
[Javascript] 연결 리스트 구현하기 (velog.io)
[Javascript] 연결 리스트 구현하기
💡 자바스크립트로 연결 리스트를 구현해보자.이번 포스트에서는 자바스크립트의 프로토타입 개념을 활용해서 연결리스트를 구현할 것이다.연결리스트의 정의와 동작원리를 이해하고 메서드
velog.io
📋 연결 리스트
📍 일반 배열과 연결 리스트
➡️ 선형적인 데이터 구조라는 점에서 비슷하다.
➡️ but 연결 리스트는 배열과 달리 요소들이 특정 메모리 주소나 인덱스에 저장되지 않는다.
📍 연결 리스트란?
➡️ 연결 리스트의 각 요소는 노드(node)라 한다.
➡️ 연결 리스트의 가장 첫 번째 지점을 헤드(head)라고 한다. 즉, 헤드는 연결 리스트의 첫 번째 노드이다.
➡️ 마지막 노드는 null을 가리킨다. 즉, 연결 리스트가 비어 있다면 헤드는 null을 참조하게 된다.
위와 같은 연결 리스트를 JS 객체로 표현하면 다음과 같이 표현할 수 있다.
const list = {
head: {
value: 6
next: {
value: 10
next: {
value: 12
next: {
value: 3
next: null
}
}
}
}
};
😃 연결 리스트의 장점
데이터 구조의 큰 틀을 바꾸지 않고도 노드를 추가하거나 삭제하기 쉽다.
😢 연결 리스트의 단점
연결 리스트는 탐색이 느리다. 배열과는 다르게 연결 리스트에서는 중간에 있는 요소에 한번에 접근하는 것이 불가하고, 첫 번째 노드부터 순차적으로 접근해야만 한다.
또, 각 노드는 포인터를 담고 있어서 배열보다 더 많은 메모리를 사용하게 된다.
📍 연결 리스트 유형
➡️ 단일 연결 리스트
각 노드가 하나의 포인터를 가지는 경우를 이야기한다.
이번 시간에 구현해 볼 것이다.
➡️ 이중 연결 리스트
각 노드가 2개의 포인터를 가지는 경우이다. 하나는 이전 노드를, 다른 하나는 다음 노드를 가리킨다.
➡️ 원형 연결 리스트
마지막 노드의 포인터가 첫 노드 또는 특정 노드를 가리키도록 만들어 루프 형태를 가지는 유형이다.
📋 JS로 연결 리스트 구현하기
💻 리스트 노드 만들기
연결 리스트의 노드는 해당 노드에 들어갈 값과 다음 노드를 가리키는 포인터 이렇게 2개의 요소를 가지고 있어야 한다.
따라서 리스트 노드는 값에 해당하는 프로퍼티와 포인터 역할을 하는 프로퍼티 이렇게 2개의 프로퍼티를 생성하여 구현할 수 있다.
class ListNode {
constructor(data) {
// 현재 노드에서의 값 저장
this.data = data;
// 다음 노드를 저장 (next는 포인터 역할)
this.next = null;
}
}
💻 연결 리스트 구현하기
📍 연결 리스트의 프로퍼티들 구현하기
헤드를 구현해보자. 헤드 노드의 초깃값은 아무것도 없는 상태로 null로 설정한다.
처음에는 요소가 아무것도 없으므로 리스트의 길이인 length 속성도 0이 된다.
class LinkedList {
constructor(head = null) {
this.head = head
this.length = 0;
}
}
이제 2개의 노드를 연결시키는 것을 구현해 보자. node1과 node2 2개의 노드를 만들어 node1에 node2를 가리키는 포인터를 만들어 주면 된다.
각각의 노드를 생성하고 연결할 때에는 맨 위에서 봤던 ListNode 클래스의 인스턴스를 만들어 생성하고, 그것을 연결 리스트로 만들 때에는 LinkedList 클래스의 인스턴스를 만들어 연결한다.
// node1 생성, 값으로 2 저장 (value)
let node1 = new ListNode(2);
// node2 생성, 값으로 5 저장 (head의 값이 5가 됨)
let node2 = new ListNode(5);
// node1의 포인터(next)가 node2를 가리키게 함. node1의 다음 노드는 node2가 됨.
node1.next = node2;
// node1과 node2가 연결된 것을 리스트로 만들기
// node1이 첫 번째 요소인 head가 되어야 하므로 LinkedList의 인자로 node1을 넣어줌.
let list = new LinkedList(node1);
// 만들어진 연결 리스트에서 노드 호출해 보기
console.log(list.head.data); // 2 (연결 리스트의 head의 data)
console.log(list.head.next.data); // 5 (head의 포인터가 가리키는 다음 노드의 값)
📍 연결 리스트의 메소드들 구현하기
➡️ size()
연결 리스트에 있는 노드들의 개수를 반환하는 메서드이다.
size() {
// 노드의 개수를 나타내는 count의 초깃값은 0
let count = 0;
// 개수는 연결 리스트의 첫 요소인 head부터 셀 것이므로 노드의 초깃값은 head
let node = this.head;
// node가 null이 되기 전까지 아래 실행문 반복
while (node) {
// count 1 증가
count++;
// node를 포인터(next)가 가리키는 다음 노드로 업데이트
node = node.next;
}
// 최종 노드 개수 반환
return count;
}
// 다음 노드가 없을 시에는 next가 null을 가리키기 때문에 node가 null로 업데이트되고 반복문의 조건이
// false가 되어 종료된다.
➡️ clear()
리스트의 요소들을 모두 삭제하여 비우는 역할을 하는 메서드이다.
단순하게 연결 리스트의 head를 null로 업데이트 하면 된다. head가 null이라는 것은 요소가 아무것도 들어 있지 않다는 의미이다.
clear() {
this.head = null;
}
➡️ getLast()
연결 리스트의 마지막 노드를 반환하는 메서드이다.
연결 리스트는 배열처럼 한번에 원하는 인덱스에 접근하지 못하므로 head부터 마지막까지 반복문을 통해 순회하여 마지막 노드를 구해야 한다.
현재 노드의 포인터가 null을 가리킨다면 그 노드가 연결 리스트에서의 마지막 노드가 된다.
getLast() {
// lastNode(현재 노드)의 초깃값은 첫 번째 요소인 head (계속해서 업데이트할 것임)
let lastNode = this.head;
// lastNode가 null이 아니면(요소가 하나도 없을 경우가 아니면) 아래 반복문 진행
if (lastNode) {
// 현재 노드의 포인터가 null을 가리키기 전까지 아래 코드 반복
while (lastNode.next) {
// lastNode를 next가 가리키는 노드로 변경
lastNode = lastNode.next
}
}
// 최종적인 lastNode 반환
return lastNode;
}
➡️ getFirst()
연결 리스트의 첫 번재 노드를 반환하는 메서드이다.
첫 번째 노드는 head이므로 단순하게 head를 반환하면 된다.
getFirst() {
return this.head;
}
➡️ append()
연결 리스트의 가장 끝에 노드를 추가하는 메서드이다.
append(value) {
// 추가할 새로운 값을 받아 새로운 노드를 생성하기
let node = new ListNode(value);
// 현재 노드 (초깃값은 첫 번째 요소인 head)
let current = this.head;
// head가 null이라면 (리스트에 요소가 하나도 없다면)
if (this.head === null) {
// 새로 생성한 노드가 head가 된다.
this.head = node;
}
// 요소가 있어 head가 null이 아니라면
else {
// 현재 노드의 다음 노드가 null이 되기 전까지 아래 반복
while (current.next != null) {
// 현재 노드를 현재 노드가 가리키는 다음 노드로 업데이트
current = current.next;
}
// 마지막 노드에 도달하면 현재 마지막 노드의 포인터가 새로 만든 노드를 가리키도록 변경
current.next = node;
}
// 노드가 하나 더 늘어났으므로 연결 리스트의 길이 증가
this.length++;
}
➡️ insert()
연결 리스트의 특정 인덱스에 노드를 추가하는 메서드이다.
// 삽입할 값과 삽입할 위치(인덱스)
insert(value, position = 0) {
// 삽입할 인덱스 값(position)으로 음수나 현재 연결 리스트의 길이보다 큰 값이 들어오면 삽입 불가능
if (position < 0 || position > this.length) {
// 따라서 false 반환
return false;
}
// 삽입할 새로운 노드 생성
let node = new ListNode(value);
// 첫 요소부터 삽입을 원하는 인덱스가 나올 때까지 순회해야 하므로 현재 노드는 첫번째로 설정
let current = this.head;
// 현재 index 또한 0부터 시작
let index = 0;
// 이전 노드의 값을 저장하기 위해 prev 변수 선언
let prev;
// 노드를 삽입하고 싶은 인덱스가 0 (리스트의 첫부분)이라면
if (position === 0) {
// 새로 생성한 노드의 포인터가 현재 리스트에서의 첫번째 노드를 가리키도록 함
node.next = current;
// 연결 리스트의 첫 번째 요소를 새로 만든 요소로 지정
this.head = node;
}
// 노드를 삽입하고 싶은 인덱스가 1 이상 this.length 이하의 범위에 있을 경우
else {
// 현재 인덱스가 삽입을 원하는 위치의 인덱스보다 더 작을 경우 아래 과정 반복
// (index++에 의해 반복문의 조건문을 지나칠 때마다 index가 1씩 증가한다.)
while (index++ < position) {
// 이전 노드값 저장 변수에 현재 노드를 저장한다. (현재 노드가 곧 이전 노드가 될 것이므로)
prev = current;
// 현재 노드는 다음 노드로 업데이트
current = current.next;
}
// 현재 index가 삽입을 원하는 index인 position에 다다르면 반복문이 종료되고
// 삽입을 위해 새로 생성한 노드의 포인터가 현재 노드를 가리키도록 함
node.next = current;
// 이전 노드의 포인터는 새로 생성한 노드를 가리키도록 함
prev.next = node;
}
// 노드가 하나 추가되었으므로 연결 리스트의 길이 1 증가
this.length++;
// 노드 삽입에 성공하였으므로 true 반환
return true;
}
➡️ remove()
연결 리스트 내에서 특정 값을 찾아 그 노드를 삭제하는 메서드이다.
삭제하고 싶은 값을 인자로 받는다.
// value 데이터를 찾아 노드를 삭제한다.
remove(value) {
// 현재 노드는 연결 리스트의 첫번째 요소부터 시작
let current = this.head;
// 이전 노드 또한 처음에는 첫번째 요소로 지정
let prev = current;
// 현재 노드의 값이 삭제하길 원하는 값이 아니면서 현재 노드의 다음 값이 null이 아니라면
// 아래의 코드 반복 (계속 앞으로 나아가야 함)
while (current.data != value && current.next != null) {
// 이전 노드는 현재 노드를 업데이트
prev = current;
// 현재 노드는 현재 노드의 다음 노드로 업데이트
current = current.next;
}
// 반복문이 끝나면 노드의 값이 삭제하길 원하는 값이 되었거나 현재 노드가 마지막 노드라는 의미이다.
// 만약 현재 노드의 값이 삭제하길 원하는 값이 아니라면 현재 노드가 마지막이라는 의미
if (current.data != value) {
// 연결 리스트에 삭제하고자 하는 노드가 존재하지 않는다는 의미로 null 반환
return null;
}
// 현재 노드의 값이 삭제하길 원하는 값이라면
else {
// 이전 노드의 다음 노드는 현재 노드의 다음 노드를 가리키는 것으로 업데이트
// 그러면 현재 노드는 연결에서 제외되게 되어 연결 리스트에서 빠지는 것이 됨
prev.next = current.next;
}
// 연결 리스트에서 노드가 하나 빠졌으므로 길이 1 감소
this.length--;
// 현재 노드의 값이 삭제하길 원하는 노드의 값이므로 그 값 반환
return current.data;
}
댓글