[자료 구조] 단일 연결 리스트(Singly Linked List)

코드 미완성

#기본 형태

---

#삽입 : O(1)

---

#삭제 : O(n)

---

#검색 : O(n)

---

@코드

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

class SinglyLinkedList() {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  } 
  
  /* 삽입 */
  insert(data, index) {
    if (!index) {  // 매개변수 index 값이 존재하지 않을 때(무조건 마지막에 추가)
      const newNode = new Node(data);  // 연결 리스트를 구성할 data 값으로 노드 생성
      if (this.head === null) {  // head가 null일 경우(연결 리스트 처음 생성)
        this.head = newNode;  // head에 newNode 할당
      } else {  // head가 null이 아닐 경우(기존이 노드가 존재)
        this.tail.next = newNode;  // 마지막 노드(tail)의 next 요소에 newNode 할당
      }
      this.tail = newNode;
    } else {  // 매개변수 index 값이 존재할 때(무조건 마지막에 추가)
      curNode = this.head
      curIndex = 0;
      if (this._size - 1 >= index - 1) {  // 필요한 것은 해당 인덱스, 해당 인덱스 - 1
        while (curNode) {
          if (curIndex === index) {
            break;
          }
          curIndex += 1;
          curNode = curNode.next;
        }
        newNode.next = curNode.next.next;
        curNode.next = newNode;
      } else {  // 현재 코드말고 error throw를 하면 좋을 것 같다.
        console.log("no data");
        this._size -= 1; 
      }
    }
    this._size += 1;
  }
  
  /* 삭제 */
  remove(value) {}
  
  /* 검색 */
  find(value) {}
  
}

---

📚 참고 자료

• 배세민, 2019, 《자바스크립트로 하는 자료 구조와 알고리즘》, 에이콘출판