Section19 - 단일 연결 리스트

---

---

날라가서 다시씀

분명 어제 저장했던 기억이 있는데, 기억만 남아버리고 파일은 날아가버렸넵

 

[단일 연결 리스트]

 

얼핏보면 배열과 같지만, 다른 점들이 짱짱많음

 

[코드]

// piece of data -val
// reference to next node - next

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

class SinglyLinkedList{
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val){

    const newNode = new Node(val);

    if(this.head === null){
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length += 1;
    
    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;
    this.tail.next = null;
    this.length -= 1;

    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;
    // currentHead.next = null;

    this.length -= 1;
    
    if(this.length === 0){
      this.head = null;
      this.tail = null;
    }

    return currentHead;
    
  }

  unshift(val){

    const newNode = new Node(val);

    if(this.length === 0){
      this.head = newNode;
      // this.head.next = newNode;
      this.tail = newNode;
    } 
    // else {

    //   const currentHead = this.head;

    //   this.head = newNode;
    //   this.head.next = currentHead;
    // }
      else {
        newNode.next = this.head;
        this.head = newNode;
  }

    this.length += 1;

    return this;

  }

  get(idx){

    if(idx < 0) return null;
    if(idx >= this.length) return null;

    let counter = 0;
    let current = this.head;

    while(counter !== idx){

      current = current.next;
      counter++;

    }

    return current;
  }

  set(idx,val){
    
    let foundNode = this.get(idx);
    
    if(foundNode){
      foundNode.val = val;
      return true;
    }

    return false;

    // const newNode = new Node(val);
    // val값만 바꿔주면 되니까 새로운 노드 만들필요 x
  }

  insert(idx,val){

    if(idx < 0) return false;
    if(idx > this.length) return false;

    if(idx === this.length) { !!this.push(val); }
    if(idx === 0){ !!this.unshift(val); } 
    //형변환 시켜버림 성공했으니까 값이뜨고 그것의 반대의 반대가 바로 true    

    const newNode = new Node(val);

    let prev = this.get(idx-1);
    let temp = prev.next
    prev.next = newNode;
    newNode.next = temp;

    
    this.length +=1;
    return true

  }

  remove(idx,val){

    if(idx < 0) return false;
    if(idx >= this.length) return false;

    if(idx === 0){ !!this.shift(val); } 
    if(idx === this.length-1) { !!this.pop(val); }

    let prev = this.get(idx-1);
    let removed = prev.next;
    prev.next = removed.next;
    // removed.next = null;
    this.length -= 1;
    
    return true;

  }

  print(){
    const arr = [];
    let current = this.head;
    while(current){
      arr.push(current.val)
      current = current.next;
    }
    console.log(arr);
  }

  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;

  }

}

 

[BigO]

 

삽입 O(1)

삭제 O(1) or O(N)

검색 O(N)

접근 O(N)

 

[Recap]

 

1.단일 연결 리스트들은 배열의 대안으로 삽입이나 삭제가 상대적으로 효율적임

2.배열과 달리 idx가 없으며 다음으로 이어지는 포인터만 있을 뿐

3.단일 연결 리스트로 이후의 나오는 스택, 큐 와 같은 자료 구조를 만들어 볼 수 있음