Home 연결리스트 Linked List
Post
X

연결리스트 Linked List

게시 2023/08/16
By Psmin
8 m읽는 시간

연결리스트에 대해 알아보자.

연결 리스트 Linked List

연결 리스트란 각 노드가 데이터와 포인터를 갖으며 한 줄로 연결되어 있는 것처럼 데이터를 관리하는 방식의 자료 구조입니다.

linked-list

연결 리스트의 종류

  • 단순 연결 리스트 Singly Linked List

    기본적인 연결 리스트로 첫 번째 노드 (Head)부터 마지막 노드 (Tail)까지 단방향으로 이어집니다.

    각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킵니다.

    singly-linked-list

  • 이중 연결 리스트 Doubly Linked List

    단순 연결 리스트에서 이전 노드를 가리키는 포인터가 추가되어 이전 노드로는 갈 수 없었던 단점을 보완한 형태입니다.

    doubly-linked-list

  • 원형 연결 리스트 Circular Linked List

    단순 열결 리스트에서 마지막 노드 (Tail)의 포인터가 첫 번째 노드 (Head)를 가리키는 형태입니다.

    circular-linked-list

단순 연결 리스트의 추상 자료형 ADT

  • addFirst : 첫 번째 노드 앞에 노드를 추가
  • addLast : 마지막 노드 뒤에 노드를 추가
  • add : 특정 위치 노드 뒤에 노드 추가
  • removeFirst : 첫 번째 노드 삭제
  • removeLast : 마지막 노드 삭제
  • remove : 특정 위치 노드 삭제
  • get : 특정 위치 노드 조회
  • set : 특정 위치 노드 변경
  • printNodeAll : 연결 리스트 안의 모드 노드의 데이터 출력
  • size : 연결 리스트의 노드 갯수
  • isEmpty : 연결 리스트가 비어있는 지 확인

구현 코드

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

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

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

  addFirst(newData) {
    let newNode = new Node(newData);

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

    this.size++;

    return newNode;
  }

  addLast(newData) {
    let newNode = new Node(newData);

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

    this.size++;

    return newNode;
  }

  add(newData, index) {
    if (index == undefined || index < 0 || index > this.size) return -1;

    let newNode = new Node(newData);

    if (index == 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let curNode = this.head;

      for (let i = 0; i < index - 1; i++) {
        curNode = curNode.next;
      }

      newNode.next = curNode.next;
      curNode.next = newNode;
    }

    this.size++;

    return newNode;
  }

  removeFirst() {
    if (this.head) {
      let rmNode = this.head;

      this.head = rmNode.next;

      this.size--;

      return rmNode;
    } else {
      return -1;
    }
  }

  removeLast() {
    let curNode = this.head;

    for (let i = 0; i < this.size - 2; i++) {
      curNode = curNode.next;
    }

    let rmNode = curNode.next;

    this.tail = curNode;
    curNode.next = null;
    this.size--;

    return rmNode;
  }

  remove(index) {
    if (index == 0) {
      this.removeFirst();
    } else {
      let curNode = this.head;

      for (let i = 0; i < index - 1; i++) {
        curNode = curNode.next;
      }

      let rmNode = curNode.next;

      curNode.next = rmNode.next;
      this.size--;

      return rmNode;
    }
  }

  get(index) {
    if (index == 0) {
      return this.head;
    } else {
      let curNode = this.head;

      for (let i = 0; i < index; i++) {
        curNode = curNode.next;
      }

      return curNode;
    }
  }

  set(newData, index) {
    if (index == 0) {
      this.head.data = newData;

      return this.head;
    } else {
      let curNode = this.head;

      for (let i = 0; i < index; i++) {
        curNode = curNode.next;
      }

      curNode.data = newData;

      return curNode;
    }
  }

  printNodeAll() {
    let curNode = this.head;
    let result = "";

    for (let i = 0; i < this.size - 1; i++) {
      result += `[ ${curNode.data} ] -> `;
      curNode = curNode.next;
    }

    result += `[ ${curNode.data} ]`;

    console.log(result);
  }

  size() {
    return this.size;
  }

  isEmpty() {
    return this.size == 0 ? true : false;
  }
}

이중 연결 리스트 구현 코드

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  addFirst(newData) {
    let newNode = new Node(newData);

    if (this.head) {
      this.head.prev = newNode;
      newNode.next = this.head;

      this.head = newNode;
    } else {
      this.head = newNode;
      this.tail = newNode;
    }

    this.size++;

    return newNode;
  }

  addLast(newData) {
    let newNode = new Node(newData);

    if (this.tail) {
      this.tail.next = newNode;
      newNode.prev = this.tail;

      this.tail = newNode;
    } else {
      this.head = newNode;
      this.tail = newNode;
    }

    this.size++;

    return newNode;
  }

  add(newData, index) {
    if (index == undefined || index < 0 || index > this.size) return -1;

    let newNode = new Node(newData);

    if (index == 0) {
      this.head.prev = newNode;
      newNode.next = this.head;

      this.head = newNode;
    } else {
      let curNode = this.head;

      for (let i = 0; i < index - 1; i++) {
        curNode = curNode.next;
      }

      newNode.next = curNode.next;
      newNode.next.prev = newNode;

      curNode.next = newNode;
      newNode.prev = curNode;
    }

    this.size++;

    return newNode;
  }

  removeFirst() {
    if (this.head) {
      let rmNode = this.head;

      this.head = rmNode.next;
      this.head.prev = null;

      this.size--;

      return rmNode;
    } else {
      return -1;
    }
  }

  removeLast() {
    let rmNode = this.tail;

    this.tail = rmNode.prev;
    this.tail.next = null;

    this.size--;

    return rmNode;
  }

  remove(index) {
    if (index == 0) {
      this.removeFirst();
    } else {
      let curNode = this.head;

      for (let i = 0; i < index - 1; i++) {
        curNode = curNode.next;
      }

      let rmNode = curNode.next;

      curNode.next = rmNode.next;
      curNode.next.prev = curNode;

      this.size--;

      return rmNode;
    }
  }

  get(index) {
    if (index == 0) {
      return this.head;
    } else {
      let curNode = this.head;

      for (let i = 0; i < index; i++) {
        curNode = curNode.next;
      }

      return curNode;
    }
  }

  set(newData, index) {
    if (index == 0) {
      this.head.data = newData;

      return this.head;
    } else {
      let curNode = this.head;

      for (let i = 0; i < index; i++) {
        curNode = curNode.next;
      }

      curNode.data = newData;

      return curNode;
    }
  }

  printNodeAll() {
    let curNode = this.head;
    let result = "";

    for (let i = 0; i < this.size - 1; i++) {
      result += `[ ${curNode.data} ] -> `;
      curNode = curNode.next;
    }

    result += `[ ${curNode.data} ]`;

    console.log(result);
  }

  size() {
    return this.size;
  }

  isEmpty() {
    return this.size == 0 ? true : false;
  }
}
코딩테스트, 자료구조
Linked List
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.

Recent Update
Link