자료구조와 알고리즘

---

💎 연결리스트

🔊 단일 연결 리스트

• 추가와 삭제가 반복되는 로직을 구현할 때 사용하는 자료구조
• 메모리의 데이터 참조방식을 응용하여 구현

📘 Node

class Node {
  constructor(newData) {
    this.data = newData; // 데이터 영역
    this.next = null; // 참조 영역
  }
}

메모리에 참조형 데이터를 할당하는 것과 비슷하게 기본노드는 데이터 영역과 참조영역으로 나누어 관리한다.

📘 class

class SingleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
}

📘 원하는 데이터를 탐색할 때

  find(data) {
    let currNode = this.head; //새로운 노드 생성
   
    while (currNode.data !== data) {  /*원하는 값을 찾을 때 까지 탐색*/
      currNode = currNode.next;
    }

    return currNode; //반환
  }

📘 마지막에 새로운 데이터 추가

  append(data) {
    const newNode = new Node(data); // 새로운 노드 생성

    if (this.head) { // 1. head에 연결된 노드가 있다면 
      this.tail.next = newNode;  // 생성된 노드를 마지막에 추가
      this.tail = newNode;       // 생성된 노드를 마지막 노드로 지정

    } else { // 2. head에 연결된 노드가 없다면
      this.head = newNode; // 생성된 노드를 첫 노드로 지정
      this.tail = newNode; // 생성된 노드를 마지막 노드로도 지정
    }
  }

📘 중간에 새로운 데이터 삽입

  insert(node, data) { // 특정 노드 다음에 새로운 노드를 삽입하고자 할떄 사용 
    const newNode = new Node(data); // 새로운 노드 생성
    newNode.next = node.next; //새로운 노드가 특정노드 이후의 노드를 가리키도록 지정 
    node.next = newNode; // 특정 노드가 생성된 노드를 가리키도록 지정
  }

📘 데이터 삭제

  remove(data) {
    const prevNode = this.head; //첫 노드를 prevNode라 하자.
    
    while (prevNode.next.data !== data) { //prevNode의 다음 노드가 원하는 값이 될떄 까지 탐색 
      prevNode = prevNode.next;
    }
    
    if (prevNode.next) { //prevNode의 다음 노드가 존재 한다면 그 다음 노드로 연결
      prevNode.next = prevNode.next.next;
    }
  }
}

📘 코드 전체

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

class SingleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  
  find(data) {
    let currNode = this.head;
    
    while (currNode.data !== data) {
      currNode = currNode.next;
    }

    return currNode;
  }

  append(data) {
    const newNode = new Node(data);

    if (this.node) {
      this.tail.next = newNode;
      this.tail = newNode;

    } else { 
      this.head = newNode;
      this.tail = newNode;
    }
  }

  insert(node, data) {
    const newNode = new Node(data);
    newNode.next = node.next;
    node.next = newNode;
  }

  remove(data) {
    const prevNode = this.head;

    while (prevNode.next.data !== data) {
      prevNode = prevNode.next;
    }

    if (prevNode.next) {
      prevNode.next = prevNode.next.next;
    }
  }
}