[자료구조] 연결리스트(linked_list) | javascript
[자료구조] 연결리스트(linked_list) | javascript
📋 [ 자료구조 ] 시리즈 몰아보기 (4)
📚 연결리스트(linked_list)
리스트의 일종으로 각 노드와 데이터가 포인터를 가지고 한 줄로 이어져있는 형태를 띄는 자료구조이다. 선형, 원형, 이중 연결 리스트로 분류되며 본 문서는 선형 연결 리스트를 다룬다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하기에 널리 사용되는 자료구조이다. 구현해야할 기능은 다음과 같다.
append(data): linked_list의 마지막에data를삽입하고 이전 레벨의 노드와연결한다.insert(data, index): linked_list의index의 위치에data를삽입하고 전후 레벨의 노드들과연결한다.delete(index): linked_list의index에 위치한 노드를제거하고 전후 레벨의 노드들과연결한다.print(): linked_list의 내용을 출력한다.search(data): linked_list에서data에 해당하는 값을 찾아 해당 노드의index값을 출력한다.clear(): linked_list를 초기화한다.length(): linked_list의 크기를 출력한다.
js에서는 Node와 LinkedList를 따로 구현하여 구현한다.
Node에서는 해당 노드에 저장할 데이터 data와 다음 노드를 가르키는 포인터 next를 할당한다.
LinkedList에서는 노드를 관리할 로직을 구현한다.
| 1 | class Node { |
| 2 | constructor(data) { |
| 3 | this.data = data; // 저장할 데이터 |
| 4 | this.next = undefined; // 다음 노드를 가르키는 포인터 |
| 5 | } |
| 6 | } |
| 7 | |
| 8 | class LinkedList { |
| 9 | ... |
| 10 | } |
🖥️ 소스코드
| 1 | class Node { |
| 2 | constructor(data) { |
| 3 | this.data = data; |
| 4 | this.next = undefined; |
| 5 | } |
| 6 | } |
| 7 | |
| 8 | class LinkedList { |
| 9 | constructor() { |
| 10 | const init = new Node("HEAD"); |
| 11 | this.head = init; |
| 12 | this.tail = init; |
| 13 | this.length = 0; |
| 14 | this.pointer = undefined; |
| 15 | } |
| 16 | |
| 17 | length() { |
| 18 | return this.length; |
| 19 | } |
| 20 | |
| 21 | append(data) { |
| 22 | const newNode = new Node(data); |
| 23 | this.tail.next = newNode; |
| 24 | this.tail = newNode; |
| 25 | this.length++; |
| 26 | } |
| 27 | |
| 28 | print() { |
| 29 | let result = ""; |
| 30 | let pointer = this.head.next; |
| 31 | for (let i = 0; i < this.length; i++) { |
| 32 | result += pointer.data + " "; |
| 33 | pointer = pointer.next; |
| 34 | } |
| 35 | result = result.split(" "); |
| 36 | result.pop(); |
| 37 | |
| 38 | return result; |
| 39 | } |
| 40 | |
| 41 | insert(data, index) { |
| 42 | const newNode = new Node(data); |
| 43 | let pointer = this.head; |
| 44 | for (let i = 0; i < index - 1; i++) { |
| 45 | pointer = pointer.next; |
| 46 | } |
| 47 | newNode.next = pointer.next; |
| 48 | pointer.next = newNode; |
| 49 | this.length++; |
| 50 | } |
| 51 | |
| 52 | delete(index) { |
| 53 | let pointer = this.head; |
| 54 | for (let i = 0; i < index - 1; i++) { |
| 55 | pointer = pointer.next; |
| 56 | } |
| 57 | pointer.next = pointer.next.next; |
| 58 | this.length--; |
| 59 | } |
| 60 | |
| 61 | search(data) { |
| 62 | let pointer = this.head; |
| 63 | for (let i = 0; i < this.length + 1; i++) { |
| 64 | if (pointer.data === data) { |
| 65 | return i; |
| 66 | } |
| 67 | pointer = pointer.next; |
| 68 | } |
| 69 | return undefined; |
| 70 | } |
| 71 | |
| 72 | clear() { |
| 73 | const init = new Node("HEAD"); |
| 74 | this.head = init; |
| 75 | this.tail = init; |
| 76 | this.length = 0; |
| 77 | } |
| 78 | } |
👨💻 관련 포스트
[자료구조] 스택(Stack) | javascript
[자료구조] 스택(Stack) | javascript
javascript로 이해하는 자료구조 [스택(stack)] : 스택(stack)은 데이터를 입력할 수 있는 선형 자료형으로 선입후출의 구조를 가지며 ctrl+z와 같은 기능에서 요구되는 자료형이다. javascript에서는 배열을 이용해 손쉽게 구현할 수 있다.
2023-04-20
[자료구조] 큐(Queue) | javascript
[자료구조] 큐(Queue) | javascript
javascript로 이해하는 자료구조 [큐(queue)] : 큐(queue)는 데이터를 입력할 수 있는 선형 자료형으로 선입선출의 구조를 가진다. 버퍼링과 같은 기능에서 요구되는 자료형이다. javascript에서는 배열을 이용해 손쉽게 구현할 수 있다.
2023-04-20
[자료구조] 덱(Deque) | javascript
[자료구조] 덱(Deque) | javascript
javascript로 이해하는 자료구조 [덱(deque)] : 덱(deque)은 스택(stack)과 큐(queue)를 합친 자료구조로 head, tail 구분 없이 양방향에서 자료를 입출력 할 수 있는 자료형이다. javascript에서는 배열을 이용해 손쉽게 구현할 수 있다.
2023-04-21
💡 로그인 하지 않아도 댓글을 등록할 수 있습니다!