자바스크립트 자료구조 - 단일 연결리스트 #1

자바스크립트로 단일 연결 리스트(Linked List) 구현하기

지난 번에 연결 리스트라는 자료구조가 어떤 것인지 살펴봤었다. C++에서는 STL 라이브러리로 지원을 하고 있지만, 자바스크립트에서는 직접 연결 리스트를 구현해서 사용해야 하는 것 같아서 여기저기 구글링해보면서 다른 분들의 코드도 한번씩 보고 이해해보려고 했다.

단일 연결 리스트

Singly Linked List

먼저 연결 리스트를 만들기 위해 필요한 코드가 무엇이 있는지 고민해보는 시간을 가졌다.

구글링해서 이미 어떤 식으로 코드를 구현했는지 보긴 했지만, 이후 스스로 고민하는 시간도 필요할 것 같아서 카피해오는 것보다 더 공부가 된다고 생각했기 때문이다.

만들 클래스

• 노드 클래스 ( data, next )
• 연결 리스트 클래스 (head, tail, size)

연결 리스트 기능

• 연결 리스트 맨 뒤에 노드 추가하기 (append)
• 연결 리스트 임의의 위치에 노드 추가하기 (insert)
• 연결 리스트 맨 뒤 노드 제거하기 (pop)
• 연결 리스트 특정 값을 가진 노드 제거하기 (remove)
• 연결 리스트 모든 요소 출력하기 (items)
• 연결 리스트 길이 출력하기 (size)

더 추가해야되는 게 있으려나..? 일단 생각나는건 이정도여서 이거로 코드 작성해보고 부족함이 생기면 추가해보기로 했다.

평소에 클래스를 사용할 일이 없어서 그런가 문법부터 헷갈렸다. ㅋㅋㅋ 세상에...! MDN 문서 보다가 class도 표현식으로 쓸 수 있다는 내용 보고 잠시 삼천포로 빠졌다가 다시 돌아오는 길이다..

Node 클래스 만들기

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

아무튼 Node 클래스로 새로운 Node 인스턴스를 만들 수 있다. 만들어진 Node의 값은 받아온 것을 그대로 사용할 것이고 다음 노드는 정해지지 않았으므로 null 값을 초기값으로 갖도록 했다.

Linked List 클래스

Linked List 클래스는 일단 생성자 부분만 먼저 작성해보았다. 중간중간 이게 맞나 확인도 해가면서 기억 안나는 부분은 관련 자료를 다시 찾아보고 수정했다.

class LinkedList {
  constructor(){
    const elem = new Node('head');
    this.head = elem;
    this.tail = elem;
    this.size = 0;
  }
}

맨 처음 연결 리스트를 만들 때 가장 앞 부분인 헤더가 있어야 또 추가하고 추가하고 할 수 있을 것이기 때문에 LinkedList로 인스턴스를 만들었을 때 head를 갖도록 하였다.

이 코드를 조금 더 파헤쳐서 들어가보면

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

가 되는 것이기 때문에 LinkedList의 constructor 안에 작성된 elem 변수는 객체 형태로 다음과 같은 속성을 가지게 된다.

const elem = {
	data : 'head',
  	next : null
}

클래스 인스턴스라 완전히 이것만 있는 채로 생기진 않았겠지만 대충 요런 느낌으로 elem이 만들어 진다.

이 상태에서 그 다음 코드인 this.head = elem 과 같은 코드는 Node 인스턴스로 만든 elem이 될 것이다.

LinkedList {
	head : {
      data : 'head',
      next : null
	},
  	tail : {
    	data : 'head',
        next : null
    },
    size : 0
}

대충 이런 구조를 가지게 된다.
그러니 뭔가 노드를 추가해서 이어 붙일 수록 LinkedList의 뎁스가 깊어지는 형태가 된다.

append()

연결 리스트 맨 뒤에 노드 추가하기

append(data){
    const newData = new Node(data);
    this.tail.next = newData;
    this.tail = newData;
    this.size++;
}

이 메서드는 파라미터로 받은 data로 새로운 노드를 하나 만든 다음에 현재 연결 리스트의 맨 마지막 자리(tail)로 만드는 메서드이다.

여기서 this.tail.next가 의미하는 것은 현재 연결 리스트의 맨 마지막 노드에게 이제는 네가 마지막이 아니야...! 너의 다음은 얘야! 라고 알려줘야 하므로 새로 만든 Node를 이 친구에게 알려주는 것이다.
그리고 진짜 마지막(마치 피피티 저장할 때 찐찐최종본..?..) 노드는 새로 만든 얘입니다~!와 같이 현재 연결 리스트의 tail 자리에 새로 만든 노드로 바꿔주는 코드이다.

그리고 노드가 추가되었기 때문에 현재 연결 리스트의 길이가 1증가 되는 코드도 작성해주었다.

pop()

연결 리스트 맨 뒤 노드 제거하기
구글링해서 봤던 코드들은 n번째 요소 제거하기 기능은 있어도 맨 마지막 노드 제거하는 코드는 못 본거 같아서 참고할 자료 없이 그냥 뇌피셜로 찌끄러본거라 맞는 코드인진 모르겠다.

pop(){
    this.tail = null;
    this.size--;
}

현재 마지막 연결 리스트의 tail의 값을 다시 null로 만들어버리고 사이즈를 줄이면 되지 않을까?

insert()

임의 위치에 노드 추가하기
이 코드는 제주코딩베이스캠프 유튜브 영상을 많이 참고했다. 머리의 한계를 느껴버려서........ㅜㅜㅜ

insert(data, idx){
  const newData = new Node(data);
  let start = this.head;

  let i = 0;
  while(i < idx - 1){
    start = start.next;
    i++;
  }

  newData.next = start.next;
  start.next = newData;

  this.size++;
}

연결 리스트는 배열처럼 인덱스가 있는 것이 아니기 때문에 순차적으로 맨 앞 head부터 하나씩 순회해야 한다.
그래서 start에는 this.head가 들어가게 된다.
while문에서 idx -1을 조건으로 넣은 이유는

idx번째 자리에 요소를 넣어야 하므로 idx - 1번째 있는 요소의 next값을 새로 넣을 노드를 가르키도록 만들어야 하기 때문이다.
그런데 idx-1 번째가 현재 가리키고 있는 다음 노드의 위치가 덮어씌워지면 추가하는 노드는 next 값을 가질 수 없게 되므로 start가 가지고 있는 next 값을 먼저 newData의 next로 넣어준 후, start의 next를 newData로 설정해주어야 한다.

글이 길어져서 2번째 글로 이어서 작성할 예정

---

참고 자료
제주코딩베이스캠프 연결 리스트
MDN class