Linked List

1. Linked List란

array와 비슷하게 여러 데이터가 한 번에 연결되어 있는 데이터 구조. 각 데이터가 value와 pointer를 통해 연결된다.

2. 형태

node: {value, next }

node--(link)-->node--(link)-->node

ex)
{start, 1} -> {1, 16} -> {16, 5} -> {5, 4}

3. 함수

class MyLinkedList {
  constructor(){ this.list = {} }
  
  //index번째 값을 받아온다.
  get = index => {
    if(Object.keys(this.list).length >= index) {
      let point = 'start';
      for(let i = 0; i < index; i++) {
        point = this.list[point];
      }
      return Number(this.list[point]);
    } else {
      return -1
    }
  }
  
  //맨 처음에 값을 추가한다.
  addAtHead = val => {
    if(Object.keys(this.list).includes('start')) {
      this.list[val] = this.list['start'];
    }
    this.list['start'] = val.toString();
  }
  
  //맨 끝에 값을 추가한다.
  addAtTail = val => {
    this.list[Object.values(this.list).filter(x => 
  Object.keys(this.list).includes(x) === false)[0]] = val.toString();
  }
  
  //index번째 자리에 값을 추가한다.
  addAtIndex = (index, val) => {
    if(Object.keys(this.list).length > index) {
      let point = 'start';
      for(let i = 0; i < index; i++) {
        point = this.list[point];
      }
      let prev = point;
      let cur = this.list[point];
      this.list[prev] = val.toString();
      this.list[val] = cur;
    }
    if(Object.keys(this.list).length == index) {
      this.addAtTail(val);
    }
  }
  
  //index번째 값을 삭제한다.
  deleteAtIndex = index => {
    let point = 'start';
    for(let i = 0; i < index; i++) {
      point = this.list[point];
    }
    let prev = point;
    let cur = this.list[point];
    this.list[prev] = this.list[cur];
    delete this.list[cur];
  }
}

4. 특징

• 논리적 순서는 순차적이나 물리적 주소는 순차적이지 않다.(배열은 논리적, 물리적 모두 순차적)
• 링크를 따라가야만 하기 때문에 데이터 접근 속도가 배열에 비해 늦다.
• 데이터를 추가할 때 논리적 주소만 바꿔주면 되기 때문에 배열에 비해 간편하다.
• 동일한 양의 데이터를 저장해도 배열에 비해 차지하는 메모리 양이 더 크다.

5. 결론

• 데이터 양이 많지만 삽입/삭제가 거의 없고, 접근을 자주해야하는 경우 → 배열
• 데이터 양이 많지 않고, 삽입/삭제를 자주 해아하는 경우 → 연결 리스트