Class의 개념이아직 익숙하지 않다면 Class에 대해 먼저 공부하고 Linked List 공부를 시작하는 것이 좋다.

Linked List에는 여러 종류가 있다.

• Singly Linked List
• Doubly Linked List
• Circular Linked List

이번에는 Singly Linked List만 다룬다.

Singly Linked List

우선 Linked List는 배열(Array)처럼 순서가 있는 자료구조이다. 하지만, 배열과는 여러 면에서 차이를 본인다.

Linked List는 배열처럼 index가 있는게 아니고 각 요소들을 가리키는 형식으로 되어있다. 그렇다보니 배열처럼 원하는 index에 바로 접근하여 값을 가져오는 것이 불가능하다.

Linked List에서 원하는 값을 가져오려면 무조건 첫 번째 요소부터 그 요소의 다음 요소 순서로 원하는 요소가 나올 때 까지 순서대로 탐색한다.

배열은 원하는 층만 누르면 바로 해당 층으로 가는 엘레베이터와 같은 반면, Linked List는 처음부터 모든 층을 거쳐서 올라가는 계단과 같다.

위의 내용을 정리하면 다음과 같다.

Linked Lists

• 인덱스가 없다
• next 라는 pointer로 각 Node가 연결되어 있다.
• 원하는 값에 바로 접근이 불가능하다.
• Insertion/Deletion이 빠르다.

Arrays

• 인덱스가 있다
• Insertion / Deletion이 느리고 비효율적이다.
• 원하는 값에 바로 접근이 쉽다.

Linked List에서 각 요소를 Node라고 부른다. 자료구조에서 Node는 Node.js의 Node가 아닌 하나의 unit이다.

각 Node 에서 저장하고 있는 값은 아래와 같다.

• head (시작 Node) - head는 list의 시작점이 있어야 하므로 필수이다.
• tail (끝 Node)
• length (list의 길이)

Singly Linked List를 그림으로 표현하면 아래와 같다.
만약, 아래 diagram에서 3에 접근하고 싶다면 첫 번째 node 인 1에서 2로 가고 2에서 3으로 가야 한다.

이제부터 Linked List를 JavaScript 코드로 직접 만들어보겠다.

먼저 나쁜 예를 보자. 😈

// BAD
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

let first = new Node("Hi");

first.next = new Node("there");
first.next.next = new Node("how");
first.next.next.next = new Node("are");
first.next.next.next.next = new Node("you");

위의 코드도 앞서 언급한 Linked List의 특성을 잘 구현했지만, 항상 저렇게 수동으로 next포인터에 꼬리를 무는 방식으로 할 수는 없다.

그래서 SinglyLinkedList 클래스를 추가로 만들어서 활용해보겠다.

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

let list = new SinglyLinkedList();

앞서 말한것과 같이 기본적으로 Linked List에는 head, tail, length가 있다.
현재 List 안에 아무 요소도 존재하지 않기 때문에 null과 0으로 선언되어있다.

이제 list에 요소들을 추가해줄 차례이다. 추가 액션중에서도 PUSH 메소드를 구현해볼건데, PUSH 메소드는 list의 맨 끝에 요소를 추가하는 액션이다.

PUSH 구현하기

1. SinglyLinkedList 클래스에 value를 인자로 받는 push 메소드를 생성한다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

	push(value) {

	}
}

2. 인자로 받은 value를 가지고 새로운 node를 생성한다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

	push(value) {
		let newNode = new Node(val);
	}
}

3. 만약 head가 없다면, 아무것도 없다는 뜻이니 새로 만든 node에 head와 tail을 지정한다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

	push(value) {
		let newNode = new Node(val);

		if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    }
	}
}

4. 만약 head가 존재한다면, 현재 tail의 next 프로퍼티에 새로운 node를 지정하고 tail을 새로운 node로 지정한다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

	push(value) {
		let newNode = new Node(val);

		if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
	}
}

5. 마지막으로 length를 1만큼 증가시킨 후 업데이트된 list를 return한다.
   여기서 this를 return하는 이유는 this가 곧 해당 인스턴스의 list이기 때문이다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

	push(value) {
		let newNode = new Node(val);

		if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

		this.length++;
    return this; // this 가 곧 list
	}
}

최종 코드(PUSH)

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val) {
    let newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
    return this;
  }
}

let list = new SinglyLinkedList();

list.push(20);
list.push(25);
list.push(31);

console.log(list);

이런식으로 추가할 때 새로운 tail만 지정해주면 tail을 찾아서 다음거에 추가해주고 새로운 tail로 바꿔주면 된다.

list 안에 무수히 많은 수의 데이터가 있더라도 tail만 찾아 해당 tail node의 next로 지정해주면 돼서 편리하다.

POP 메소드

POP메소드는 tail node를 제거후 return한다.
tail을 제거 후 바로 전 node를 새로운 tail로 지정해줘야 한다는 점이 걸린다. (Singly Linked Lists 에서는 다음을 가리키는 next만 존재하므로)

아래의 순서로 구현할 수 있다.
1. 아무 node도 존재하지 않는다면 undefined를 return
2. tail을 찾을 때 까지 loop를 처음부터 순서대로 돈다.
3. tail node를 찾으면 바로 전 node를 새로운 tail로 지정하고 next 값을 지정한다.
4. length에서 1을 빼준다.
5. 방금 제거한 node의 value를 return한다.