스터디 발표 준비 - 단일연결리스트(Singly Linked List)

• 단일 연결 리스트 정의
• 단일 연결 리스트와 Array 비교
• 검색, 삽입, 제거, 순회

LinkedList

데이터를 저장하는 자료구조

index로 접근하는 array와 달리 LinkedList는 인덱스 없이 그냥 다수의 data element

즉, node로 구성 → 데이터에 접근할 index는 없기 때문에 첫번째 element부터 차례로 탐색

각각의 node는 문자열, 숫자와 같은 하나의 data element를 저장한다. + 다음 node를 가리키는 정보 역시 저장. 다음 노드가 없는 마지막 노드는 null을 가리킨다. 중간 node는 일일이 추적하지 않는다. head만 알고 있을 것이다.

구성

1. head → linked list의 시작 node
2. tail → 마지막 node
3. length → 작업 용이를 위해 유지

단지 다음 노드들을 가리키고 있는 수많은 노드들이라고 봐도 된다.

엘레베이터 없는 고층 건물(각 층이 계단으로만 연결 되어 있는)

비주알고를 많이 이용할 것

vs Array

LL는 index가 없다. head만 있을 뿐. tail이 필수는 아니지만 head는 필수

각 node는 next pointer를 통해 연결

임의 접근(Random access)은 불가 == 가령 10번째 항목에 접근하려 할 때 바로 그 값을 얻을 수 없다.

새로운 항목 추가, 제거에 용이한 자료구조

array에서 shift되는 경우를 생각해보자.

저장만 하면 되는 정보가 있을 때, 삽입, 제거만 해주면 될 때 용이한 자료구조

---

push method

• 맨 끝에다가 Node를 넣어준다.
• head가 없으면 push 해준 Node가 head이면서 tail
• push 될 때마다 길이도 1씩 증가
• tail.next가 새로운 Node, tail도 해당 Node로 갱신

pop method

• push와 쌍
• 맨 마지막 Node 제거 즉, tail 제거, 반환 길이 감소
• tail도 갱신해야 하기 때문에 head부터 따라가야 한다. 까다롭다.
• 엣지 케이스들을 생각해주자. head 조차 없는 빈 LinkedList일 경우, head 1개만 있을 때

shift method

• head 제거 비교적 쉽다. 길이 감소
• 엣지 케이스 생각. Node가 없을 경우

unshift method

• shift와 쌍
• 새로운 Node를 head에 추가, 길이도 1씩 증가
• head 갱신

get method

• 특정 index의 Node 반환
• 유효하지 않은 index(0보다 작거나 길이(this.length)와 같거나 클 때)는 null 반환

set method

• get과 쌍
• get이용 받아온 Node 갱신
• boolean 반환

insert method

• set과 비슷해보이지만, 갱신하던 set과 달리 새로운 Node 삽입하는 것
• get에서와 다르게 길이와 같을 경우는 push와 같은 역할
• 마찬가지로 0에서는 unshift와 같은 역할
• get으로 찾아오는 것보다 전의 Node 찾아야 하므로 -1
• 길이 1증가
• boolean 반환

remove method

• insert와 쌍
• 길이-1과 같으면 pop
• 0이면 shift
• get으로 index-1찾기
• 길이 1 감소

reverse method

• 별로 유용하지는 않지만 일단 있는 내용이고, 많이 물어본다고..
• 작업하는 중에 정보 손실이 발생하지 않도록 주의!

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  traverse() {
    let current = this.head;
    while (current) {
      console.log(current.val);
      current = current.next;
    }
  }
  push(val) {
    let newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = this.tail.next;
    }
    ++this.length;
    return this;
  }
  pop() {
    if (!this.head) return undefined;
    let current = this.head;
    let newTail = current;
    while (current.next) {
      newTail = current;
      current = current.next;
    }
    this.tail = newTail;
    newTail.next = null;
    --this.length;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return current;
  }
  shift() {
    if (!this.head) return undefined;
    let currentHead = this.head;
    this.head = currentHead.next;
    --this.length;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return currentHead;
  }
  unshift(val) {
    let newHead = new Node(val);
    if (!this.head) {
      this.head = newHead;
      this.tail = newHead;
    } else {
      newHead.next = this.head;
      this.head = newHead;
    }
    ++this.length;
    return this;
  }
  get(index) {
    if (index < 0 || index >= this.length) return null;
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    return current;
  }
  set(index, val) {
    let foundNode = this.get(index);
    if (!foundNode) return false;
    foundNode.val = val;
    return true;
  }
  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);
    newNode.next = prev.next;
    prev.next = newNode;
    ++this.length;
    return true;
  }
  remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === this.length - 1) return !!this.pop();
    if (index === 0) return !!this.shift();

    let prev = this.get(index - 1);
    let toRemove = prev.next;
    prev.next = toRemove.next;
    --this.length;
    return toRemove;
  }
  reverse() {
    let node = this.head;
    this.head = this.tail;
    this.tail = node;
    let next;
    let prev = null;
    for (let i = 0; i < this.length; ++i) {
      next = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }
    return this;
  }
  print() {
    let arr = [];
    let current = this.head;
    while (current) {
      arr.push(current.val);
      current = current.next;
    }
    console.log(arr);
  }
}

Big O

삽입 - O(1)

제거 - Head는 O(1)

→ 그냥 Array보다 상기 2개가 장점

+뭘 제거하려는지에 따라서 정해지긴 하지만 그 외에는 O(n)으로 생각해야함

검색, 접근 - O(n)

 

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

 

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */

const removeNthFromEnd = (head, n) => {
  let sz = 0;
  for (let node = head; !!node; node = node.next) {
    ++sz;
  }
  if (n === sz) {
    head = head.next;
  } else {
    let curNode = head;
    let nextNode = curNode.next;
    for (let i = 1; i < sz - n; ++i) {
      curNode = nextNode;
      nextNode = curNode.next;
    }
    curNode.next = nextNode.next;
  }
  return head;
};

https://leetcode.com/problems/add-two-numbers

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

const addTwoNumbers = (l1, l2) => {
  let sum = 0n,
    tenSqr = 1n;
  for (let node = l1; !!node; node = node.next) {
    sum += BigInt(node.val) * BigInt(tenSqr);
    tenSqr *= 10n;
  }
  tenSqr = 1n;
  for (let node = l2; !!node; node = node.next) {
    sum += BigInt(node.val) * BigInt(tenSqr);
    tenSqr *= 10n;
  }
  const head = new ListNode(sum % 10n);
  sum /= 10n;
  let current = head;
  while (sum > 0) {
    current.next = new ListNode(sum % 10n);
    current = current.next;
    sum /= 10n;
  }
  return head;
};

 

더 똑똑하게 풀어보자 좀.. 자바스크립트에는 기본 library가 없으니.. 불편한 것 같다. 일일이 어떻게 구현해서 사용하지