[Data Structure] Linked List - 링크드 리스트 ( 연결 리스트 )

링크드 리스트는 기본적인 노드 개념을 처음으로 학습하게 되는 자료구조이다. 링크드 리스트는 하나의 노드가 자신의 값과 다음 노드를 가리키는 포인터, 이 두 가지만 가지고 있다. 따라서, 한 번 지나간 노드는 이전 노드로 돌아갈 수 없다는 게 포인트이다.

 

 

Linked List ( 링크드 리스트 / 연결 리스트 )

위에서 언급했고, 위 그림에서 볼 수 있듯이 가장 기본이 되는 개념은 노드이다.

 

하나의 노드는 value와 next 두가지로 이루어져 있다.

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

링크드 리스트는 이 노드의 연결로 이루어진 자료구조이다.

이 노드의 next에 새로운 노드를 넣어줌으로써 노드간에 연결이 생긴다. 그리고 이것은 일종의 Direction graph의 일종이 된다.

 

만약 새로운 노드를 추가한다고 하면, 아래처럼 first 노드의 next에 second 노드를 담아주는 걸로 간단한 연결 리스트를 만들 수 있다.

const first = new Node(2);
const second = new Node(4);

first.next = second;

 

하지만, 연결리스트를 자료구조처럼 언제든지 꺼내쓰기 위해서는 당연하게도 추상화가 필요하다. 이것은 OOP의 개념이므로 여기서 굳이 언급하진 않겠다. 지금은 추상화란 여러번 꺼내 먹어도 변하지않는 마법의 도구 정도로만 대충 이해하자.

 

여튼 결론적으로 노드의 개념만 확실하게 잡고, 노드간의 연결이 연결 리스트라는 개념을 잡고나면 그냥 넣어주면 끝나는 아주 간단한 자료구조이다.

 

그럼 대체 왜 이런 자료구조를 사용할까?

 

간단한 예로 ppt가 있다. 우리는 발표할 때 앞에서 뒤로 넘겨준다. ( 때에 따라 뒤로 가는 경우도 있지만 그건 곧 이어서 설명하겠다. )

앞 장의 ppt에서 제목을 썼다면, 다음 장의 ppt에서는 내용이나 사진을 보여줘야 할 거다. 링크드 리스트는 이런 구조의 명칭이다.

 

Doubly Linked List ( 더블리 링크드 리스트 / 이중 연결 리스트 )

더블리 링크드 리스트는 노드의 구성이 다른 경우이다.

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null; // 추가
    this.next = null;
  }
}

이전을 가리키는 포인터가 하나 더 추가된 형태로, 드디어 우리가 일상적으로 만나는 모습이 되었다. 이중 연결 리스트는 어디서 자주 보는걸까? 위에서 예로 든 ppt도 사실은 이전과 다음으로 이동할 수 있다. 이것은 이전 페이지의 다음페이지에 다음 페이지라는 노드를 추가해두었기 때문이다.

 

const head = new Node(1);
const second = new Node(2);
const third = new Node(3);

head.next = second;
second.prev = head;
second.next = third;
third.prev = second;

위의 코드를 실행하면 아래의 그림처럼 변한다.

디테일을 잘 보자. next는 다음 노드 자체 ( 큰 박스 )를 가리키고, prev는 이전 노드 자체 ( 큰 박스 )를 가리킨다.

안의 숫자는 head, second, third의 value이다.

 

너무 간단해서 별로 설명할 게 없다.

자료구조에 따라 하나의 노드를 어떤 식으로 구성하는 지가 결정된다.

반대로, 노드를 보고 어떤 자료구조일 지 유추하는 것도 가능하다. 물론 이 경우에는 완벽하진 않겠지만.

 

차차 다른 자료구조도 포스팅하도록 하겠다.