단일 연결리스트

reference: 출처

linked list 란?

• head(linked list의 시작 node), tail(마지막 node), length를 가지고 있는 자료구조

• 다음 데이터 element를 가리키는 index없이(접근할 index 없음), 다수의 data element(node)로 구성

• 각 node는 value와 pointer를 가지고 있고 string 혹은 number 형태로 저장

• 각 node는 다음 node를 가리키는 정보 역시 저장하고 있어야 하며, 다음 node가 없을 경우, null이 저장

• head node → second node → third node를 알아내는 식으로 마지막 node까지 접근. 따라서 특정 node에 접근하고 싶다면 head node부터 시작

• 삽입과 제거를 쉽게 할 수 있다

연결리스트 vs 배열

종류	크기	참조성능	수정성능	공간복잡도	시간복잡도
배열	정적	좋음	안 좋음	좋음	O(1)
연결리스트	동적	안 좋음	좋음	안 좋음	O(n)

• 배열은 10층으로 바로 갈 수 있는 엘리베이터

• 연결리스트는 10층까지 순서대로 걸어 올라가야 한다.

---

연결리스트 메서드 활용

**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);
    // head가 없다면 새로운 node를 head, tail로 할당
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
      // head가 있다면 새 node를 tail의 다음 list로 할당
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    // list의 length
    this.length += 1;
    return this;
  }
}

const list = new SinglyLinkedList();

// list.push(1)
// > SinglyLinkedList {head: Node, tail: Node, length: 1}

// list.head
// > Node {val: 1, next: null}

// list.tail
// > Node {val: 1, next: null}

// list.push(10)
// > SinglyLinkedList {head: Node, tail: Node, length: 2}

// list.tail
// > Node {val: 10, next: null}

// list.head.next
// > Node {val: 10, next: null}

// 현재 list는 1 - 10 의 형태

pop 메서드

pop() {
    if (!this.head) return undefined;
    let current = this.head;
    let newTail = current;
    // 현재 node의 next node가 있을 때까지 반복
    while (current.next) {
      // 다음 node가 있다면
      // 현재 node를 newTail로 할당
      newTail = current;
      // 현재 node의 next를 현재 node로 할당
      current = current.next;
    }
    // 다음 node가 없다면 newTail을 this.tail에 할당
    this.tail = newTail;
    // this.tail의 다음 node를 null로 설정함으로써
    // 1. 이후에 아무것도 없다고 알려주고
    // 2. '!'에 대한 연결을 끊는다
    this.tail.next = null;
    this.length--;

    // head만 남은 상황에서 pop 메서드를 사용하면 head, tail 모두 null
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return current;
  }

// pop 메서드

// list.pop()
// > Node {val: '!', next: null}

// list.pop()
// > Node {val: 'goodbye', next: null}

// list.pop()
// > Node {val: 'hello', next: null}

// list.pop() undefined

shift 메서드

shift() {
    // head가 없으면 return
    if (!this.head) return undefined;
    // 현재 head를 currentHead로 할당
    let currentHead = this.head;
    // currentHead의 다음 node를
    this.head = currentHead.next;
    this.length--;

		if (this.length === 0) {
      this.tail = null;
    }
    return currentHead;
  }

// shift 메서드
// list.shift()
// Node {val: 'hello', next: Node}

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 2}head: Node {val: 'goodbye', next: Node}length: 2tail: Node {val: '!', next: null}[[Prototype]]: Object

// list.shift()
// > Node {val: 'goodbye', next: Node}

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 1}

unshift 메서드

unshift(val) {
    // 새로운 node 생성
    let newNode = new Node(val);
    // head가 없으면 새 node를 head에 할당, 기존 head를 tail에 할당
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    }
    // 현재 head를 새 node의 다음 node로 할당
    newNode.next = this.head;
    // 그리고 새 node를 현재 head로 할당
    this.head = newNode;
    this.length++;
    // 전체 list return
    return this;
  }

// unshift 메서드
// list.unshift('first')
// > SinglyLinkedList {head: Node, tail: Node, length: 4}
//   head: Node {val: 'first', next: Node}
//   length: 4
//   tail: Node {val: '!', next: null}

get 메서드

get(index) {
    // index가 0보다 작고 또는 list 길이보다 크거나 같으면 null
    if (index < 0 || index >= this.length) return null;
    let counter = 0;
    // list의 head를 current값으로 할당
    let current = this.head;
    // counter가 index값과 같지 않을때까지 '현재 node의 다음 node'를 current node에 할당하며 반복
    while (counter !== index) {
      current = current.next;
      counter++;
    }
    return current;
  }

// get 메서드
// list.get(-2)
// > null

// list.get(6)
// > null

// list.get(3)
// > Node {val: 'what', next: Node}

set 메서드

set(index, val) {
    // get 메서드로 index를 찾고 foundNode에 할당
    let foundNode = this.get(index);
    // foundNode가 있으면 val값을 foundNode의 val값에 저장하고 true 반환 그렇지 않으면 false반환
    if (foundNode) {
      foundNode.val = val;
      return true;
    }
    return false;
  }

// set 메서드
// list.get(3)
// > Node {val: 'what', next: Node}

// list.set(3, 'oh')
// > true

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 5}head: Node {val: 'hello', next: Node}length: 5tail: Node {val: 'the', next: null}[[Prototype]]: Object

// list.get(3)
// > Node {val: 'oh', next: Node}

// list.set(6, 'asdasd')
// > false

**insert 메서드**

insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return this.push(val);
    if (index === 0) return this.unshift(val);

    let newNode = new Node(val);
    let prev = this.get(index - 1);
    let temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
  }
// 1. 입력한 index가 0보다 작거나 list 길이보다 크면 false
// 2. 입력한 index가 list의 길이와 같으면 list 끝에 새로운 node를 추가한다
// 3. 입력한 index가 0이면 새로운 node(val)를 list의 맨 앞에 unshift한다

// 4. 입력한 값의 node(val)를 newNode 변수에 할당한다
// 5. insert하려는 index를 찾기 위해서 get 메서드를 사용해 index - 1 값의 node를 prev 변수에 할당한다
// 6. val를 담을 node(prev.next)를 temp에 할당한다
// 7. 이 temp node를 새로 생성한 node의 next에 할당한다

const list = new SinglyLinkedList();

list.push(100);
list.push(201);
list.push(250);
list.push(350);

// insert
// list.insert(0, 'first');
// > SinglyLinkedList {head: Node, tail: Node, length: 5}

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 5}head: Node {val: 'first', next: Node}length: 5tail: Node {val: 350, next: null}

// list.get(4)
// > Node {val: 350, next: null}

// list.insert(5, 'last')
// > SinglyLinkedList {head: Node, tail: Node, length: 6}head: Node {val: 'first', next: Node}length: 6tail: Node {val: 'last', next: null}

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 6}head: Node {val: 'first', next: Node}length: 6tail: Node {val: 'last', next: null}

// list.get(5)
// > Node {val: 'last', next: null}

remove 메서드

특정 index의 node를 제거

remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    let prev = this.get(index - 1);
    let removed = prev.next;
    prev.next = removed.next;
    this.length--;
    return removed;
  }
// 1. 입력한 index값이 0보다 작거나 list 길이보다 크면 undefined
// 2. 입력한 index값이 0이면 shift메서드를 사용해 제거
// 3. 입력한 index값이 tail이면 pop메서드 사용해 제거

// 4. get메서드를 사용해 제거하려는 index 전의 node를 prev에 할당
// 5. prev의 다음 node를 removed(제거할) 변수에 할당
// 6. removed(제거할) node의 다음 node를 prev의 다음 node에 할당

// remove 메서드
// list.remove(0)
// > Node {val: 100, next: Node}

// list.remove(2)
// > Node {val: 350, next: null}