[Javascript] LinkedList 연결 리스트 구현하기

단일 연결 리스트

각 노드에 1개의 자료 공간과 저장공간을 가지며 각 노드의 포인터는 다음 노드를 가리킨다.

자료공간

저장공간

====>

자료공간

저장공간

====>

자료공간

저장공간

기본적인 노드 구조

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

가장 기본적인 노드 구조이며 연결 리스트를 만들때 사용할 용도입니다.

class LikedList {
  constructor() {
    let init = new node("init");
    this.head = init;
    this.tail = init;
    this.size = 0;
  }}

연결리스트의 초기 모습이며, 이때는 처음과 끝 그리고 리스트 갯수를 나타낼수 있는 변수들을 정의 해줍니다.

노드 연결해주기

// 맨 앞에 하나씩 추가하기
unshift(data) {
    let newnode = new node(data);
    let current = this.head;
    newnode.next = current.next;
    current.next = newnode;
    if(this.tail.data === "init"){
      this.tail = newnode;
    }
    this.size++;
  }

unshift라는 함수를 만들었는데 이 함수의 기능은 노드를 가장 앞에 연결해주는 기능을 가지고 있습니다.

  // 마지막에 하나씩 추가하기
  push(data) {
    let newnode = new node(data);
    let current = this.head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = newnode;
    this.tail = newnode;
    this.size++;
  }

push 함수는 가장 기본적인 노드 연결 방식이며 노드 끝에 새로운 노드를 연결해주는 기능을 가지고 있습니다.

  // 원하는 위치에 하나씩 추가하기
  insert(data, location) {
    let newnode = new node(data);
    let current = this.find(location);
    newnode.next = current.next;
    current.next = newnode;
    this.size++;
    while (current.next != null) {
      current = current.next;
    }
    this.tail = current;
  }
  find(location) {
    let current = this.head;
    while (current.data != location) {
      current = current.next;
    }
    return current;
  }

insert 함수는 원하는 위치에 새로운 노드를 연결해주는 기능을 가지고 있습니다.

노드 제거하기

  // 앞에꺼 하나씩 제거하기
  shift() {
    let current = this.head;
    current.next = current.next.next;
    this.size--;
  }

shift 함수는 가장 앞에있는 노드를 제거해주는 기능을 가지고 있습니다.

  // 맨뒤에꺼 하나씩 제거하기
  pop() {
    let current = this.head;
    while (current.next.next != null) {
      current = current.next;
    }
    current.next = null;
    this.tail = current;
    this.size--;
  }

pop 함수는 마지막에 있는 노드를 제거해주는 기능을 가지고 있습니다.

  // 원하는 위치 하나씩 제거하기
  splice(location) {
    let current = this.head;
    let currentpre = this.head;
    let last = this.head;
    while (current.data != location) {
      current = current.next;
    }
    while (currentpre.next.data != location) {
      currentpre = currentpre.next;
    }
    currentpre.next = current.next;
    while (last.next != null) {
      last = last.next;
    }
    this.tail = last;
    this.size--;
  }

splice 함수는 원하는 위치의 노드를 제거해주는 기능을 가지고 있습니다.

  // 원하는 값 수정하기
  change(location, change_value){
    let current = this.head;
    while(current.data != location){
      current = current.next;
    }
    current.data = change_value;
  }

change 함수는 원하는 값을 수정해주는 기능을 가지고 있습니다.

노드의 값을 배열로 받아오기

  printArr(){
    let current = this.head;
    let arr = [];
    while(current.next!= null){
      arr.push(current.next.data);
      current = current.next;
    }
    return arr;
  }

printArr 함수는 연결된 노드의 data 값을 배열로 반환해주는 기능을 가지고 있습니다.

노드의 전체 길이를 받아오기

  printLength(){
    return this.size;
  }

printfLength 함수는 size를 이용하여 전체 길이를 반환해주는 기능을 가지고 있습니다.

---

전체 코드

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

class LikedList {
  constructor() {
    let init = new node("init");
    this.head = init;
    this.tail = init;
    this.size = 0;
  }
  // 맨 앞에 하나씩 추가하기
  unshift(data) {
    let newnode = new node(data);
    let current = this.head;
    newnode.next = current.next;
    current.next = newnode;
    if(this.tail.data === "init"){
      this.tail = newnode;
    }
    this.size++;
  }
  // 마지막에 하나씩 추가하기
  push(data) {
    let newnode = new node(data);
    let current = this.head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = newnode;
    this.tail = newnode;
    this.size++;
  }
  // 원하는 위치에 하나씩 추가하기
  insert(data, location) {
    let newnode = new node(data);
    let current = this.find(location);
    newnode.next = current.next;
    current.next = newnode;
    this.size++;
    while (current.next != null) {
      current = current.next;
    }
    this.tail = current;
  }
  find(location) {
    let current = this.head;
    while (current.data != location) {
      current = current.next;
    }
    return current;
  }
  // 앞에꺼 하나씩 제거하기
  shift() {
    let current = this.head;
    current.next = current.next.next;
    this.size--;
  }
  // 맨뒤에꺼 하나씩 제거하기
  pop() {
    let current = this.head;
    while (current.next.next != null) {
      current = current.next;
    }
    current.next = null;
    this.tail = current;
    this.size--;
  }
  // 원하는 위치 하나씩 제거하기
  splice(location) {
    let current = this.head;
    let currentpre = this.head;
    let last = this.head;
    while (current.data != location) {
      current = current.next;
    }
    while (currentpre.next.data != location) {
      currentpre = currentpre.next;
    }
    currentpre.next = current.next;
    while (last.next != null) {
      last = last.next;
    }
    this.tail = last;
    this.size--;
  }
  // 원하는 값 수정하기
  change(location, change_value){
    let current = this.head;
    while(current.data != location){
      current = current.next;
    }
    current.data = change_value;
  }
  // 전체 값을 배열로 리턴하기
  printArr(){
    let current = this.head;
    let arr = [];
    while(current.next!= null){
      arr.push(current.next.data);
      current = current.next;
    }
    return arr;
  }
  // 전체 길이 리턴하기
  printLength(){
    return this.size;
  }
}

let a = new LikedList();
a.unshift(1); // head : 1 tail : 1
a.unshift(2); // head : 2, 1 tail : 1
a.push(3); // head : 2, 1, 3 tail : 3
a.insert(99,2); // head : 2, 99, 1, 3 tail : 3
a.pop(); // head : 2, 99, 1 tail : 1
a.change(99, 5); // head : 2, 5, 1 tail : 1
a.splice(5) // head : 2, 1 tail : 1
a.shift() // head : 1 tail : 1
let b = a.printArr();  // [1]
let c = a.printLength(); // 1
console.log(a);