게시글

5만명이 선택한 평균 별점 4.9의 제로초 프로그래밍 강좌! 로드맵만 따라오면 됩니다! 클릭
강좌10 - Algorithm - 8년 전 등록 / 일 년 전 수정

자료구조(연결 리스트, linked list)

안녕하세요. 이번 시간부터는 잠깐 화제를 돌려 자료구조에 대해 알아보고 가겠습니다.

자료구조는 데이터의 표현 및 저장 방법을 의미합니다. 알고리즘은 그 저장된 데이터를 처리하는 과정이고요. 즉, 자료구조를 알아야 알고리즘을 배울 수 있습니다. 하지만 지금까지 우리는 자료구조를 배우지 않았는데도 알고리즘을 배웠습니다. 제가 또 거짓말을 한 걸까요? 지난 시간에 우리는 계속 자료구조를 썼습니다. 다만 그게 자료구조였다는 것을 눈치채지 못했을 뿐이죠.

바로 배열이 자료구조 중 하나입니다. 그리고 자료구조의 대부분을 혼자서 다 해먹습니다. 자료구조에는 연결리스트, 스택, 큐 등이 있는데 자바스크립트의 배열은 훌륭하게도 이 모든 것을 표현할 수 있습니다. 그래서 문제가 되는 것이 자료구조를 배울 때 자바스크립트는 도움이 되지 않습니다. 이미 만능 배열이 있거든요. 굳이 연결리스트, 스택, 큐를 직접 구현할 필요가 적습니다.

하지만 그렇다고 해서 배울 필요가 아예 없다는 것은 아닙니다. 자료구조를 배우고, 직접 구현하다보면 생각하는 힘(프로그래밍 사고력)이 길러집니다. 그리고 어떤 때 어떤 자료구조를 쓰는 게 최선인지도 알게 됩니다. 같이 한 번 배워봅시다.

이번 시간에는 가장 기본인 연결 리스트에 대해 배워봅시다. 연결 리스트는 여러 개의 노드(Node.js 아님)로 이루어져 있습니다. 각각의 노드는 일종의 객체로 데이터와 다음 노드가 뭔지 알려주는 주소를 가지고 있습니다. 또한 연결 리스트에는 새로운 데이터를 추가(add)하거나, 데이터의 위치를 찾거나(search), 제거(remove)하는 기능이 있어야 합니다.

1->2->3->4->5 라는 연결 리스트가 있다면 1,2,3,4,5는 데이터고 ->는 주소입니다. 안타깝게도, 이미 자바스크립트에는 이것이 구현되어 있습니다. 바로 배열입니다. [1,2,3,4,5]가 있으면 1,2,3,4,5는 데이터이고, array[0], array[1] 등은 데이터가 담긴 위치를 말해주고 있죠. 또한, array.push();를 통해 데이터를 추가할 수 있고, array.splice();를 통해 데이터를 제거할 수 있습니다.

하지만 이렇게 바로 배열을 써버리면 공부가 안 되겠죠? 우리는 조금 고통을 받더라도 객체를 통해 직접 구현할 겁니다. 즉, 자바스크립트의 배열을 우리 손으로 직접 만드는 과정입니다.

일단 연결 리스트와 노드를 만들어봅시다.

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

class LinkedList {
  length = 0;
  head = null;    
}

LinkedList에는 length와 head가 있습니다. length는 노드의 개수를 표현하는 부분이고, head가 바로 첫 노드의 주소를 가리키는 부분입니다. 이제 데이터를 추가(add), 검색(search), 삭제(remove)하는 메소드를 구현해봅시다.

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

class LinkedList {
  length = 0;
  head = null;

  add(value) {
    if (this.head) {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = new Node(value);
    } else {
      this.head = new Node(value); 
    }
    this.length++;
    return this.length;
  }
  search(index) {
    return this.#search(index)[1]?.value;
  }
  #search(index) {
    let count = 0;
    let prev;
    let current = this.head;
    while (count < index) {
      prev = current;
      current = current?.next;
      count++;
    }
    return [prev, current];
  }
  remove(index) {
    const [prev, current] = this.#search(index);
    if (prev && current) {
      prev.next = current.next;
      this.length--;
      return this.length;
    } else if (current) {
      // index가 0일 때
      this.head = current.next;
      this.length--;
      return this.length;
    }
    // 삭제하고자 하는 대상이 없을 때
    // 아무것도 안 함
  }
}

물론 추가할 때는 굳이 마지막에 추가하지 않아도 되고, 중간에 끼워넣는다든지, 맨 처음에 끼워넣어도 되겠죠? 직접 구현해보세요. 이제 테스트를 한 번 해볼까요?

const list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.length; // 3
list.search(0); // 1
list.search(2); // 3
list.remove(1);
list.search(2); // undefined
list.length; // 2

배열과 비슷하게 동작하는 것을 확인할 수 있습니다. 시간 복잡도를 생각해봅시다. 맨 앞에 추가하는 것은 O(1)이고 뒤에 추가하는 것은 O(n)입니다. 반복문이 있나 세어보면 됩니다. 맨 뒤에 추가하는 것도 O(1)로 만들고 싶다면 head처럼 tail 속성을 추가하면 됩니다. 데이터를 찾는데는 O(n), 데이터를 제거하는 데는 O(n), 중간에 넣는 데는 O(n)이 소요됩니다. 공간 복잡도도 O(n)입니다.

특수한 연결 리스트도 있습니다. 현재 연결 리스트는 한 쪽 방향으로만 이동합니다. 그래서 다시 뒤로 가기는 불편하죠. 이걸 해결한 리스트가 이중 연결 리스트입니다. next외에 this.prev를 넣어 이전 노드를 가리키게 한 겁니다. 구현은 조금 더 복잡해지지만, 한 번 구현하면 그 뒤로는 편하게 앞과 뒤로 노드를 왔다갔다할 수 있습니다. 또 지금은 하나의 데이터씩만 연결되지만 한 노드에서 여러 노드를 연결하는 다중 연결 리스트도 있습니다. this.next를 노드들의 배열로 만들면 되겠죠? 필요에 따라 조금씩 변형해서 쓰시면 됩니다.

다음 시간에는 스택에 대해서 알아보겠습니다!

조회수:
0
목록
투표로 게시글에 관해 피드백을 해주시면 게시글 수정 시 반영됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright 2016- . 무단 전재 및 재배포 금지. 출처 표기 시 인용 가능.
5만명이 선택한 평균 별점 4.9의 제로초 프로그래밍 강좌! 로드맵만 따라오면 됩니다! 클릭

댓글

8개의 댓글이 있습니다.
일 년 전
add(value) {
const node = new Node(value);
let current = this.head;
if (!current) {
this.head = node;
this.length++;
return node;
} else {
while (current.next) {
current = current.next;
}
current.next = node;
this.length++;
return node;
}
}

안녕하세요. 위 코드에서 계속 return node; 를 해주고 있는데
node 를 계속 리턴하는 이유가 뭘까요 ?
remove 함수에서는 remove 를 리턴하던데
어떤 이유로 해당 값을 리턴하는지 알 수 있을까요?
일 년 전
return 값은 아무거나 주셔도 됩니다. 저는 보통 추가한 노드나 제거한 노드를 return 해서 다른 곳에서 쓸 수 있게 만듭니다.
일 년 전
넵! 답변 감사합니다
5년 전
add의 if문 끝에 return node 라는 부분이있는데
if문에서 변경된 값은 LinkedList()객체속 값인데
var node = new Node(value);에 값을 return해서 무슨 의미가 있는건가요?
5년 전
var node = list.add(2); 해서 나중에 node.data로 값에 접근할 수 있습니다.
6년 전
current.next가 갑자기 어디서 나온건가요? ㅠ
6년 전
current가 현재 노드고 current.next가 다음 노드입니다.
6년 전
이것도 개인적인 생각일지 모르겠지만.. remove 메서드에 while안에서 remove를 계속해서 변경할 필요는 없는거 같습니다.
while (count \u003c position) {
before = current;
current = current.next;
count++;
}
remove = current;
before.next = remove.next;
6년 전
그렇네요~ 감사합니다!
6년 전
add 메소드도 if 에서 조기리턴 하기때문에 else 구문을 굳이 사용할 필요 없어요 보입니다.

LinkedList.prototype.add = function(value) {
let node = new Node(value);
let current = this.head;
if (!current) {
this.head = node;
this.length++;
return node;
}

while (current.next) {
current = current.next;
}
current.next = node;
this.length++;
return node;
};
6년 전
네 return이 붙으면 else를 생략해도 되죠. 이건 그냥 코딩 취향이라고 보시면 되겠습니다.
6년 전
remove 메소드에 count 선언시 var 빠져있습니다.
6년 전
감사합니다~
7년 전
remove 기능에서 while(count\u003c position) { 아랫줄에 current = current.next; 가 빠진 것 같습니다!
7년 전
감사합니다~
7년 전
LinkedList.length 값은 length가 예약어여서 값이 제대로 반영되지 않습니다. (node v7.3.0 에서 테스트)
7년 전
음 이상하네요. length는 배열이나 유사배열일 경우만 예약어이거든요. node v7.10.0에서 해봤는데 잘 작동합니다.