23/10/17 TIL __ 링크드 리스트

 
 

🚗  링크드 리스트

 

• 유동적으로 연결고리를 떼었다가 붙였다가 할 수 있는 자료구조
• 링크드 리스트 요소의 삽입/삭제에 강점이 있다. 
• 빈번하게 데이터를 삽입/삭제 해야하는 경우에 사용하면 좋다. 

 
 
 
 

🧐  배열   vs   링크드 리스트

• 이와 반대로 배열의 경우 데이터를 삽입/삭제 과정이 번거롭다. 요소 변경 후, 재정렬이 이루어 진다. 
• 빈번하게 데이터를 접근 하는 경우 배열을 사용하는 것이 좋다. 인덱스 값에 따라 한번에 값을 찾기 때문.

 
 
 
 
 
예시) __ 각 노드들을 연결하기

class Node {
  constructor(data) {
    this.data = data;

    //포인터로 사용할 값이 필요해서 만듬.
    this.next = null;
  }
}

class LinkedList {
  constructor(value) {
    //헤드로 시작할 값을 연결하기 위해 만듬.
    this.head = new Node(value);
    this.nodeCount = 0;
  }

  //노드를 붙여주면서 연결하기 위해 만듬.
  append(value) {
    let curr = this.head;

    //curr.next가 null인 경우를 계속 하나하나 보면서 찾는거임.
    while (curr.next !== null) {
      curr = curr.next;
    }
    
    //newNode 라는 변수를 선언하고, 거기에 새로 만든 node를 집어넣음.
    const newNode = new Node(value);
    //헤드 노드의 next 값으로 방금 만든 newNode 넣어줌.
    curr.next = newNode;
    // 링크드리스트 몇개정도 노드가 있는지 셈. _ get, add 할때 유효성 검사에 용이
    this.nodeCount++;
  }
}

 
위 예시에서, while 문 부분이 정말 이해가 안갔었다. 
분명 next는 null이랬는데, 왜 null이 아닌 경우가 나올때까지 반복하는 건지 모르겠었다. 
 
 
 
답은 바로 아래에 있었다. 
 

바로 아래에서 기존에 있던 노드에 새로운 노드를 붙여줄 때에, 
.next값으로 다음 노드를 지정해 준다.  __이렇게 __>>>  curr.next = newNode;
이 while 문에서는, null인 경우만을 찾기 때문에, 
지금 이 반복문 안에는 이미 .next에 그다음 노드가 들어가 있다.

 
 
 
 
링크드리스트 에서 값을 가져오고, 추가하는 부분까지 아래 예시에 나와있다

전체 예시)
 

class Node {
  constructor(data) {
    this.data = data;

    //포인터로 사용할 값이 필요해서 만듬.
    this.next = null;
  }
}

class LinkedList {
  constructor(value) {
    //헤드로 시작할 값을 연결하기 위해 만듬.
    this.head = new Node(value);
    this.nodeCount = 0;
  }

  //노드를 붙여주면서 연결하기 위해 만듬.
  append(value) {
    let curr = this.head;

    //curr.next가 null인 경우를 계속 하나하나 보면서 찾는거임.
    while (curr.next !== null) {
      curr = curr.next;
    }
    //newNode 라는 변수를 선언하고, 거기에 새로 만든 node를 집어넣음.
    const newNode = new Node(value);
    
    //헤드 노드의 next 값으로 방금 만든 newNode 넣어줌.
    curr.next = newNode;
    
    // 링크드리스트 몇개정도 노드가 있는지 셈. _ get, add 할때 유효성 검사에 용이
    this.nodeCount++;
  }


  //링크드리스트 에서 원하는 요소를 가져오는 메소드
  getNode(index) {
    //해당 인덱스가 유효한 값인지 nodeCount 의 값이랑 비교해야함.
    if (index > nodeCount) {
      console.log("linkedList 의 크기보다 벗어난 값 입니다.");
    } else {
      //index가 유효한 값인 경우 아래 실행.

      //node에 링크드리스트의 시작 노드를 넣어주고,
      let node = this.head;
      
      //원하는 인덱스 요소에 도달할 때 까지 계속 반복하며 노드들을 지나옴.
      for (let i = 0; i < index; i++) {
        node = node.next;
      }
      
      //결국 도달한 노드 리턴.
      return node;
    }
  }
}