[Data Structure]Linked List

연결리스트(Linked List)

연결리스트는 일련의 원소를 배열처럼 차례대로 저장되지만 , 원소들이 메모리상에 연속적으로 위치하지 않는다는 점이 다르다.

• 연속되는 항목들이 포인터로 연결된다.
• 마지막 항목은 Null을 가리킨다.
• 필요한 만큼 길어질 수 있다.
• 메모지 공간을 낭비 하지 않느다.
• 배열의 비해 데이터의 추가및삭제가 용이하다
• 순차적으로 탐색하기 때문에 일반적으로 탐색 속도가 떨어진다.

데이터와 다음을 가르키는 노드를 가지고 있다.
단일 연결 리스트와 이중 연결 리스트가 존재 한다.
단일연결리스트는 형태가 한쪽 방향으로 전개되고 head와 tail이 분명히 존재 한다.
이중 연결 리스트는 양쪽으로 방향 전개가 가능하다.

addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가합니다.
remove(value) - 주어진 값을 찾아서 연결을 해제(삭제)합니다
getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의하세요. 해당 인덱스에 노드가 없다면 undefined를 반환합니다.
contains(value) - 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
indexOf(value) - 주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.

addToTail(value)

addToTail(value) {
  const node = new Node(value) // 노드추가
  if(this.head === null){//요소가 없는상태서 추가
    this.head = node;//머리에 꼬리에 추가
    this.tail = node;// 꼬리는 이제 새로들어온 노드 
  }else{//요소가 원래 있던경우
    this.tail.next = node;//꼬리다음에 추가 
    this.tail = node;// 꼬리는 이제 새로들어온 노드  
  }
  this._size ++;// 전체 사이즈 추가 
  return this;
}

remove(value)

remove(value) {
    let curr = this.head//현재노드
    let prev = this.head//이전노드 
    if(this.head.value === value){// head를 삭제하는 경우
      this.head = this.head.next
    } 
    else {// 헤드이후의 값이 삭제 되는 경우 
      while(curr.value !== value){
        prev = curr
        curr = curr.next//현재노드는 현재의 다음 노드 
      }
      prev.next = curr.next//꼬리는 새로운 노드 
    }
    this._size --
  }

getNodeAt(index)

let count = 0;
let node = this.head;
while (count !== index){
  count ++;
  node = node.ndxt;
  if(index > this._size) {
    return undefined;
  }
}
reutrn node;
}

contains(value)

contains(value) {
    let count = 0;
    let node = this.head;
    while (node.value !== value) {
      count++;
      node = node.next;
      if (this._size <= count) {
        return false;
      }
    }
    return true;
  }

indexOf(value)

indexOf(value) {
    let count = 0;
    let node = this.head;
    while (node.value !== value) {// 찾는 값이 같지 않을때 반복끝
      count++; // 카운트가 위치를 나타냄 
      node = node.next; //노드를 다음으로 옮긴다. 
      if (this._size <= count) {
        return -1;
      }
    }
    return count;
  }