자료구조 ) 연결리스트로 배열의 단점을 해결하기

작성일 In Views: Disqus:

▪︎ 연결리스트 (Linked List)

image.png

연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료 구조입니다. 이름처럼 데이터를 담고있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 됩니다.

연결리스트는 배열과 비교하여 구조를 변경하고 데이터를 삽입 삭제하는데에 있어 효율적인 처리가 가능합니다. 예를들어 배열의 앞쪽에 새로운 데이터를 추가하는 push 메서드, 배열의 앞쪽의 데이터를 삭제하는 shift 메서드는 인덱스의 변경으로 인해 O(N)의 시간복잡도로 처리됩니다. 그러나 연결리스트에서 같은 동작을 수행한다면 새로운 노드를 생성하고 그 노드의 포인터만 앞쪽 노드로 가리켜주면 되기 때문에 O(1)의 시간복잡도로 처리가 가능합니다.

▫︎ 연결리스트의 구현

자바스크립트에서 연결리스트의 구현은 3단계로 구분할 수 있습니다.

  1. 노드 클래스 생성
  2. 연결리스트 클래스 생성
  3. 연결리스트 메서드 추가

이 때 노드를 정의하면서 다음 노드의 위치를 가리키는 포인터만을 정의한다면 단방향 연결리스트, 이전 노드의 위치를 가리키는 포인터를 추가로 정의한다면 양방향 연결리스트를 만들 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 노드 클래스 생성
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    // this.prev = null;
  }
}
// 연결리스트 클래스 생성
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // 필요한 연결리스트의 메서드들을 추가
  add(value) {
    const node = new Node(value);

    if (this.head) {
      this.tail.next = node;
      // node.prev = this.tail;
    } else {
      this.head = node;
    }

    this.tail = node;
    this.length++;
    return node;
  }

  remove() {
    this.head = this.head.next;
    // this.head.prev = null;
    this.length--;
  }

  getHead() {
    return this.head.value;
  }
}

▪︎ Example of Apply

image.png

image.png

▫︎ 일반적인 배열 조작으로 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
const fs = require("fs");
const input = fs.readFileSync("linkedlist.txt").toString().trim();
const cards = Array(+input)
  .fill(0)
  .map((_, idx) => idx + 1);
// cards = [1,2,3,4,5,6]

while (cards.length > 1) {
  cards.shift();
  cards.push(cards.shift());
}

console.log(...cards); // output: 4

위 코드의 while문 한번의 시행에서 배열의 원소 중 하나만이 삭제되기 때문에 N-1번의 시행 횟수를 가집니다. 또한 while문 안에서 카드의 앞 요소를 삭제하는 shift 메서드는 배열의 길이만큼 순회하게됩니다. 따라서 O(N^2)의 시간복잡도를 가지며 이것은 입력에 따라 시간제한 2초 (2*10^8)를 초과할 수 있으므로 조건에 맞는 풀이가 아닙니다. 따라서 O(N)의 시간복잡도로 풀 수 있도록 연결리스트 자료구조를 적용해보겠습니다.

▫︎ 연결리스트 자료구조를 적용하여 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const fs = require("fs");
const input = fs.readFileSync("linkedlist.txt").toString().trim();

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

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

  add(value) {
    const node = new Node(value);

    if (this.head) {
      this.tail.next = node;
      node.prev = this.tail;
    } else {
      this.head = node;
    }

    this.tail = node;
    this.length++;
    return node;
  }

  remove() {
    this.head = this.head.next;
    this.head.prev = null;
    this.length--;
  }

  getHead() {
    return this.head.value;
  }
}

const cards = new LinkedList();
for (let i = 1; i <= +input; i++) {
  cards.add(i);
}

while (cards.length > 1) {
  cards.remove();
  cards.add(cards.getHead());
  cards.remove();
}

console.log(cards.getHead());