728x90

Linked List의 정의(Definition of Linked List)

Linked Lists Data Structure Image

🎈 위 그림에서 볼 수 있듯, Linked List는 기본적으로 NodeHead(or Tail까지)로 구성되어 있다.
NodeDataNext로 구성되어 있는데, Data는 해당 노드의 데이터 Next는 다음 Node를 가리키는 Reference를 가지고 있다.
그리고 Linked List의 맨 앞 Node는 Head가 가리키며, 맨 끝 Node는 Tail이 가리키고 있다.

Linked Lists의 method는 만들기 나름이지만, 이 글에서는 insertFirst(data), size(), getFirst(), getLast(), clear(), removeFirst(), removeLast(), insertLast(data), getAt(index), removeAt(index), insertAt(data, index) 를 다뤄볼 것이다.

https://github.com/DasolPark/Algorithm_DataStructure_JavaScript-Stephen-/blob/master/completed_exercises/linkedlist/directions.html
(자세한 Node class API, LinkedList class API 내용은 위 링크를 확인해주세요)

JavaScriptclass를 이용하여 NodeLinked List를 만들어보겠다.

Node class

😐 Node class는 위처럼 data, next로 구성했다. next는 값이 언제 들어올지 모르므로 default 설정해준다.
(default가 궁금하다면 JavaScript - ES2015를 참고해주세요)

Linked List class 1

😐 Linked List의 constructor()는 head만 선언해주었다. this.head의 시작은 항상 null.

insertFirst() method가장 첫 번째 list에 Node를 생성해 준다.
가장 첫 번째 List에 넣어줘야하므로, this.head에 Node를 생성해준다. 기존에 첫 번째 값이 존재할 수 있으므로, next에는 this.head를 넣어줘서, 이전에 this.head가 가리키고 있던 (과거)첫 번째 노드를
새로 만든 첫 번째 Node가 가리킬 수 있도록 reference를 재설정해준다.

size() methodlist의 크기를 알려준다.
while loop을 이용해 node를 끝까지 탐색하게 해주고, node를 이동할 때마다 counter를 1개씩 증가시켜주면 된다.

getFirst() methodlist의 첫 번째 node를 반환한다.
간단하게, this.head를 반환해주면 된다. 만약 list가 비어있다면 null이 반환될 것이다.

getLast() methodlist의 마지막 node를 반환한다.
if 조건문을 이용해, list가 비어있다면 null을 반환해준다.
비어있지 않다면, while loop을 이용해 node를 끝까지 탐색하여 마지막 node를 반환해준다.
여기서 중요한 것은 while loop안에 if 조건문으로, 탐색중인 node의 다음 node가 없다면,
해당 node가 마지막이므로 바로 반환
할 수 있도록 작성해주는 것이다.

clear() methodlist를 초기화한다.
this.head = null;을 작성해주면 간단하게 해결할 수 있다.

Linked List class 2

removeFirst() method가장 첫 번째 node를 제거해준다.
this.head첫 번째 node를 가리키고 있고, this.head.next두 번째 node를 가리키고 있다.
따라서, this.head에 두 번째 노드인 this.head.next를 넣어주면, 첫 번째 노드는 제거된다.
(list 그림을 상상해야한다. head가 첫 번째 노드를 가리키다가, 두 번째 노드를 가리킨다고 생각하면 된다)

removeLast() method가장 마지막 node를 제거해준다.
list가 비어있을 경우, list에 node가 하나일 경우를 먼저 조건문으로 처리해줘야 한다.
(previous와 node를 사용할 것이므로 적어도 node가 2개 이상 돼야 한다.)
탐색을 하기 전에, 제거할 node의 이전 node를 가리키는 previous, 제거할 node인 node를 선언해준다.
while loop안에서 지금까지 해왔던 탐색과 마찬가지로 node를 이용해 마지막 node를 찾은 후,
previous.next에 null을 넣어줘서 마지막 node를 제거해준다.

insertLast(data) methodlist의 가장 마지막에 node를 생성해 준다.
직접 작성해줄 수도 있겠지만, 여기서 이전에 작성한 method를 재사용해줄 수 있다. 바로 getLast() method다.
마지막 node를 찾아줄 getLast()를 사용하고, 만약 last가 있다면 last의 다음에 node를 생성해주고,
만약 last가 없다면 list가 비었다는 것이므로, this.head에 node를 생성해주면 된다.

Linked List class 3

getAt(index) method원하는 index의 node를 찾아준다.
size() method를 작성할 때와 비슷하게, counter를 선언해주고 while loop을 이용해 탐색한다.
while loop 안에서 if 조건문을 이용해 만약 index와 counter가 같다면 해당 node를 반환해준다.
while loop 안에서 못 찾았다면, index값이 list의 개수를 벗어나거나, list가 비어있는 것이므로 null을 return해준다.

removeAt(index) method해당 index의 node를 제거해준다.
해당 node를 제거하려면 이전 node도 알아야하기 때문에 적어도 node가 2개 이상이어야 한다.
따라서 list가 비어있을 경우list에 node가 1개만 있을 경우를 조건문으로 처리해준다.
그리고 여기서도 기존 method를 재사용할 수 있다. 바로 this.getAt(index)이다.
this.getAt(index-1)을 이용해 previous를 찾아내고, previous가 탐색 범위가 넘어갔을 경우를 조건문으로 처리해준다.
!previous는 아예 범위가 벗어난 경우, !previous.next는 previous는 찾아냈지만, previous가 마지막 node인 경우다.
만약 위의 조건문에 걸리지 않는다면,
정상적으로 해당 node 제거가 가능하다는 것이므로, previous.next에 previous.next.next를 넣어준다.
이렇게 처리해주면, previous와 previous.next.next 사이에 있던 node를 제거할 수 있다.

insertAt(data, index) method해당 index에 node를 생성해준다.
여기서도 해당 index의 이전 node를 가리키는 previous를 사용해줘야 하기 때문에,
list가 비어있을 경우, list에 node가 1개만 있을 경우를 조건문으로 처리해준다.
이전과 다르게, 위의 조건문에 걸렸을 경우에는 바로 node를 생성해주고 return한다.
여기서는 2개의 기존 method를 재사용해줄 수 있다. 바로 getAt()getLast()이다.
getLast()를 사용하면 insertAt에 list의 범위를 넘어간 index를 넣었을 때, list의 가장 마지막에 node를 생성해줄 수 있다.
previous.next를 가리키는 node를 생성해주고, previous.next에 새로운 node를 넣어주면 된다.
(머릿속으로 Linked List이미지를 상상하자)

🎉 위의 방법으로 JavaScript를 이용해 Linked List를 작성해줄 수 있다.
다음 글에서는 Linked List를 이용한 Algorithm들을 살펴보겠다.

Full Code

class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
 
class LinkedList {
constructor() {
this.head = null;
}
 
insertFirst(data) {
this.head = new Node(data, this.head);
}
 
size() {
let counter = 0;
let node = this.head;
 
while (node) {
counter++;
node = node.next;
}
 
return counter;
}
 
getFirst() {
return this.head;
}
 
getLast() {
if (!this.head) {
return null;
}
 
let node = this.head;
while (node) {
if (!node.next) {
return node;
}
node = node.next;
}
}
 
clear() {
this.head = null;
}
 
removeFirst() {
if (!this.head) {
return;
}
 
this.head = this.head.next;
}
 
removeLast() {
if (!this.head) {
return;
}
 
if (!this.head.next) {
this.head = null;
return;
}
 
let previous = this.head;
let node = this.head.next;
while (node.next) {
previous = node;
node = node.next;
}
previous.next = null;
}
 
insertLast(data) {
const last = this.getLast();
 
if (last) {
// There are some existing nodes in our chain
last.next = new Node(data);
} else {
// The chain is empty!
this.head = new Node(data);
}
}
 
getAt(index) {
let counter = 0;
let node = this.head;
while (node) {
if (counter === index) {
return node;
}
 
counter++;
node = node.next;
}
return null;
}
 
removeAt(index) {
if (!this.head) {
return;
}
 
if (index === 0) {
this.head = this.head.next;
return;
}
 
const previous = this.getAt(index - 1);
if (!previous || !previous.next) {
return;
}
previous.next = previous.next.next;
}
 
insertAt(data, index) {
if (!this.head) {
this.head = new Node(data);
return;
}
 
if (index === 0) {
this.head = new Node(data, this.head);
return;
}
 
const previous = this.getAt(index - 1) || this.getLast();
const node = new Node(data, previous.next);
previous.next = node;
}
 
forEach(fn) {
let node = this.head;
let counter = 0;
while (node) {
fn(node, counter);
node = node.next;
counter++;
}
}
 
*[Symbol.iterator]() {
let node = this.head;
while (node) {
yield node;
node = node.next;
}
}
}

+ Recent posts