[프로그래머스 FE 데브코스/TIL] 단일 연결 리스트

가장 먼 노드 코딩테스트 문제를 오늘 강의들으면서 같이 풀어봤는데 그래프 구조의 문제를 푸는게 처음이었어서 생소하더라구요. 여러번 연습을 해봐야 겠어요. 그리고 트리, 힙, 트라이, 정렬 알고리즘과 자료구조들에 대해서 공부했습니다. 평소에 자동완성 기능이 어떤식으로 작동하는 지 궁금했는데 트리(trie)구조 더라구요? 주말에 한번 구현해보려구요!
오늘 부터 다음주 화요일까지 첫번째 과제 수행 기간이에요. 전회 순회, 중회 순회, 후위 순회를 구현하는 건데 이렇게만 봐서는 아직 감도 잡히지 않습니다. 😎 구글링 열심히 해봐야 겠어요... 
이전에 공부했던 자료구조와 알고리즘 구현 코드를 오늘 다시 연습해봤습니다. 

 

🔗  단일 연결 리스트 구현

 

착각했던 부분이 첫번째 노드가 head가 되는줄 알았는데 head 포인터(header)가 따로 존재하고 head 포인터에 첫번째로 연결될 노드의 주소값이 저장되어 있는 거더라구요. 하지만 강사님께서는 head 포인터 없이 첫번째 node를 head라고 하고 구현하신거 같습니다. 

 

 

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

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

}

const linkedList = new SinglyLinkedList();
console.log(linkedList);

//출력 결과
SinglyLinkedList {head: null, tail: null}

 

head와 tail이 잘 들어가 있습니다. 하지만 노드가 하나도 없는 상태이기 때문에 null로 자리를 채워준 상태입니다. 

node 추가 기능(append)을 추가해 봅시다.  

만약 노드가 하나도 없는 경우에는 this.head === null 상태 입니다. 이 경우 노드를 하나 추가하게 되면 첫번째 노드가 head이자 tail이 됩니다. head node(=tail node)에는 넣어준 값만 들어간 상태이고 next 주소는 비어있겠죠?

만약 노드뒤에 노드를 추가해서 연결하는 경우에는 현재 tail인 노드의 next 주소 부분에 새로운 노드의 정보(newNode)가 들어가겠죠?

그리고 새로 추가된 노드가 tail이 됩니다. 

 

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

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

  append(newValue) {
    const newNode = new Node(newValue);
    if(this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
}

const linkedList = new SinglyLinkedList();
linkedList.append(1);
console.log(linkedList);

//출력 결과
SinglyLinkedList {head: Node, tail: Node}
>head: Node {value: 1, next: null}
>tail: Node {value: 1, next: null}

 

✔️ 노드 추가 append

노드를 몇개 더 추가해 볼게요!

헤드노드에 next 노드 주소 정보가 잘 들어갔고 tail도 잘 없데이트 되었네요. tail의 next 값이 null 인것도 잘 확인이 됐어요.

 

const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
console.log(linkedList);

//출력 결과
SinglyLinkedList {head: Node, tail: Node}
>head: Node {value: 1, next: Node}
	>next: Node {value: 2, next: Node}
	>value: 1
>tail: Node {value: 3, next: null}

 

✔️ 노드 삭제

노드를 삭제하기 위해서는 삭제를 원하는 노드(target node)의 직전노드(prevNode)의 next 주소 값을 삭제를 원하는 node(target node) 다음 노드의 주소로 바꿔주면 됩니다. 그러면 target node는 연결리스트 연결과는 떨어지기 때문에 자연히 사라집니다.