Linked List

Linked List🤮

사전지식

• Storage ➡️ (HDD/SSD) 가격이 저렴하며 용량이 크고 전원이 꺼져도 데이터가 저장됨

• Memory ➡️ (DRAM) 가격이 비싸고 용량이 적고 전원이 꺼지면 데이터가 사라짐 But 속도가 빠르다

• CPU ➡️ 데이터를 끌어다 쓸때 Storage가 아닌 Memory안의 데이터를 끌어다 씀 ( Memory가 속도가 빠르기 때문 )

Array List ➡️ [추가/삭제 : 느림 ( 메모리주소를 한칸한칸씩 땡겨야하기때문 )] [인덱스 조회: 빠름 ( 주소를 알고있음 )]

Linked List ➡️ [추가/삭제 : 빠름 ( 연결만 재설정 해주면되기때문 )] [인덱스 조회: 느림 ( 하나하나 타고 조회해야함 )]

• node ➡️ dataField + linkField 그림에서는 총 4개의 node가 존재함 (JS는 객체지향이므로 이것을 객체로 표현)

• data field ➡️ 실제 값

• link field ➡️ 다음 node가 무엇인가에 대해 저장되어있음

• Head ➡️ 첫번쩨 node가 무엇인가에 대해 저장되어있음

실제로 만들어보기

test.js

const LinkedList = function () {
  this.head = null;
  this.size = 0;
};

const Node = function (data) {
  this.data = data;
  this.link = null;
};

앞으로 찍어낼 객체를 만들 함수들

LinkedList.prototype.add = function (data) {
  const newNode = new Node(data);
  if (this.head === null) {
    this.head = newNode; // Node { data: 5, link: null } // 헤드에 주소넣어주기
    this.size++;
  } else {
    let currentNode = this.head;
    while (currentNode.link !== null) {
      currentNode = currentNode.link;
    }
    currentNode.link = newNode;
    this.size++;
  }
};

생성자에 의해 생성될 객체가 사용할 수 있게 프로토타입으로 add 함수 구현

add() ➡️ 링크리스트에 값을 넣어주는 함수로 디자인함

1. 노드객체를 생성 한다.

2. head값이 null이라면 head에 새로 생성한 노드를 넣는다.

3. head값이 있다면 링크를 타고타고 들어가 링크값이 null일때, 즉 마지막 노드의 값에 새로 생성된 노드를 넣는다.

LinkedList.prototype.insertFirstNode = function (data) {
  const newNode = new Node(data);
  newNode.link = this.head;
  this.head = newNode;
  this.size++;
};

insertFirstNode() ➡️ 첫번째노드에 ‘값이 추가되도록’ 디자인함

1. 노드객체를 생성 한다.

2. 생성된 노드객체의 링크값으로 현재의 head값을 넣어준다.

3. 현재의 head값은 새로운 노드객체의 값으로 대체되어진다.

LinkedList.prototype.insertMiddleNode = function (data, index) {
  const newNode = new Node(data);
  let beforeNode = this.head;
  while (--index !== 0) {
    beforeNode = beforeNode.link;
  }
  let afterNode = beforeNode.link;
  beforeNode.link = newNode;
  newNode.link = afterNode;
  this.size++;
};

insertMiddleNode() ➡️ 첫번째 노드를 제외한 어느곳에서나 ‘값이 추가되도록’ 디자인함

1. 노드객체를 생성 한다.

2. beforeNode를 생성하여 현재 head의 값을 넣어준다.

3. 전달받은 index값을 통해 값이 추가되어야할 자리의 바로 앞 노드객체를 beforeNode에 넣어준다.

4. beforeNode에를 통해 알아낸 그 다음 노드객체를 새로생성한 afterNode에 저장한다.

5. 각 링크들을 알맞게 재정의해준다.

LinkedList.prototype.delete = function (index) {
  let beforeNode = this.head;
  if (index >= 1) {
    while (--index !== 0) {
      beforeNode = beforeNode.link;
    }
    let tobeDelete = beforeNode.link;
    let afterNode = beforeNode.link.link;
    beforeNode.link = afterNode;
    delete tobeDelete;
  } else {
    let tobeDelete = beforeNode;
    let afterNode = beforeNode.link;
    this.head = afterNode;
    delete tobeDelete;
  }
  this.size--;
};

delete() ➡️ 어느곳이든 상관없이 노드를 삭제하고 재정의하게 디자인함.

1. index값이 1 이상이라면 노드를 재정의해준다.

2. index값이 그 외 라면 head를 재정의해준다.

LinkedList.prototype.showData = function () {
  let currentNode = this.head;
  const result = Array(this.size).fill(0);
  for (let i = 0; i < this.size; i++) {
    result[i] = currentNode.data;
    currentNode = currentNode.link;
  }
  return result;
};

showData() ➡️ 링크리스트를 배열로 재정의하여 볼 수 있게 디자인함.

1. fill(value, start, end) ex) fill(5,0,3) 5라는 숫자로 0~3의 인덱스까지 채워주셈.

2. 즉 fill(0) 0이라는 숫자로 전부다 채워주셈.

const a = new LinkedList();
a.add(1); // [1]
a.add(5); // [1,5]
a.add(4); // [1,5,4]
a.insertMiddleNode(3, 2); // [1,5,3,4]
a.delete(0); // [5,3,4]
console.log(a.showData());

결과는 성공적.

class 문법으로 코드카타 풀어보기

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

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

  addAtHead(val) {
    const newNode = new Node(val);
    if (this.head === null) {
      this.head = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.size++;
  }

  addAtTail(val) {
    const newNode = new Node(val);
    if (this.tail === null) {
      this.tail = newNode;
      let currentNode = this.head;
      while (currentNode.next !== null) {
        currentNode = currentNode.next;
      }
      currentNode.next = this.tail;
    } else {
      let last = this.tail;
      last.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  addAtIndex(index, val) {
    if (index <= this.size - 1) {
      const newNode = new Node(val);
      let beforeNode = this.head;
      while (--index !== 0) {
        beforeNode = beforeNode.next;
      }
      let afterNode = beforeNode.next;
      beforeNode.next = newNode;
      newNode.next = afterNode;
      this.size++;
    } else {
      return;
    }
  }

  deleteAtIndex(index) {
    let beforeNode = this.head;
    if (index >= 1) {
      while (--index !== 0) {
        beforeNode = beforeNode.next;
      }
      let afterNode = beforeNode.next.next;
      delete beforeNode.next;
      beforeNode.next = afterNode;
    } else {
      let afterNode = beforeNode.next;
      delete beforeNode.next;
      this.head = afterNode;
    }
    this.size--;
  }

  get(index) {
    let currentNode = this.head;
    while (index !== 0) {
      if (currentNode.next) {
        currentNode = currentNode.next;
      } else {
        return -1;
      }
      index--;
    }
    return currentNode.val;
  }
}

성공!!