Judaeng

Data Structure(2) Linked List(연결 리스트) 본문

Base/자료 구조

Data Structure(2) Linked List(연결 리스트)

Judaeng 2021. 3. 14. 00:33

리스트 자료구조는 데이터를 나란히 저장하며, 중복된 데이터의 저장을 막지 않는다.

리스트는 수학적으로 중복을 허용하지 않는 '집합'과는 다르다.

리스트라는 자료구조는 구현 방법에 따라서 다음과 같이 크게 두 가지로 나뉜다.

선형 리스트(Linear List) : 배열을 기반으로 구현된 리스트(배열 리스트)

연결 리스트(Linked List) : 노드의 연결로 구현된 리스트

 

Linked List (연결 리스트)

List(리스트)는 데이터에 순서를 매겨둔 자료 구조이다. 

데이터들이 순서대로 쭉 늘어진 모양을 하고 있다.

데이터들은 차례대로 줄을 서고 있을 뿐 서로에 대해 모르는 상태이다.

Linke list의 DATA element, node

 

Linked List(연결 리스트)는 데이터들이 연락처를 주고 받아 자기 뒤에 있는 사람에게 연락을 할 수 있게 된 상태이다.

누군가를 건너뛰거나 뒤를 돌아서 앞사람에게 연락을 할 수는 없다.

오직 자기 뒷사람에게만 연락할 수 있다.

 

다시! Linked List는 순서가 있는 DATA Collection이다.

하나의 data는 node로 표현되는데 각 node는 두 가지 필드를 가지고 있다.

  • 저장될 데이터의 값을 가진 필드 : data, value, information 등으로 불린다.
  • 다음 노드의 주소를 가진 필드 : next, next pointer, next link라고 하고 다음 노드를 가리킨다.

 

연결 리스트에 일렬로 연결된 데이터들을 각각 노드(node)라고 한다. 

이 노드들은 각각 데이터와 다음 노드 정보를 갖는다.

연결 리스트는 한마디로 노드(node)로 이루어진 자료 구조이고, 각 노드는 index를 갖지 않는다.

리스트는 배열과는 달리 오직 원소(node)들 간의 논리적인 순서에 대한 정보만 가진 자료구조이기 때문에 자기 다음 데이터(next)가 무엇인지만 알고 있다.

 

다른 데이터와 연결되려면 노드(node) 어딘가에 다음 데이터에 대한 정보를 기억하고 있어야 하지 않을까?

이렇게 자기 다음 데이터의 정보를 가지는 변수를 '포인터 변수'라고 하는데 여기서는 next라는 변수가 이에 해당한다.

노드에는 자기 자신의 값이 담긴 데이터 변수, 그리고 다음 데이터를 가리키는 포인터 변수(next)가 들어있다.

연결 리스트의 맨 처음의 노드를 머리 노드(head)라고 하며, 마지막 노드를 꼬리 노드(tail)라 부르기도 한다.

꼬리 노드(tail)는 맨 뒤에 위치하기 때문에 뒤에 아무도 없는 상태이다.

꼬리 노드는 next변수에는 null이 들어가게 된다.

 

Linked List의 활용

 

흩어져 있는 데이터를 pointer로 연결하여 자료구조를 만든다.

데이터를 추가하고 삭제하는 예시를 보면 Linked List를 어떻게 활용하는지에 대한 감을 잡아보자.

 

시간 복잡도(Big-O)

[추가/삭제] 연결 리스트는 데이터를 추가하거나 삭제할 때 효율적이기 때문이다.

탐색 과정 이후에, 임의의 지점에 데이터를 추가하거나 삭제하는 데에는 O(1)의 시간이 걸린다.

엄밀히 말하면 경우에 따라 다르다고 하는 게 맞고, 대부분의 경우 O(n)의 시간이 걸린다고 본다.

 

[탐색] 위에서 한 가지 주의해야 할 점은 '탐색 과정 이후'라는 말인데, 연결 리스트는 순차 접근 방식을 사용해 탐색을 하기 때문에 앞선 노드들을 모두 거쳐야만 해당 노드의 데이터를 알 수 있다.

탐색은 최악의 경우 O(n)이라는 시간이 걸릴 수 있게 되는 것이다.

 

 

연결 리스트 vs 배열

 

연결 리스트는 특히 배열과의 차이점에 대해 아는 것이 중요하다.

삽입과 삭제가 자주 필요한 상황에는 LinkedList(연결 리스트)를 사용하는 것이, 데이터에 바로바로 접근하는 것이 중요한 상황이라면 Array(배열)을 사용하도록 하자.

Array의 예

Array는 아이템 하나를 추가, 삭제하는 데에도 다른 데이터들의 위치가 모두 변경되어야 하기 때문에 비효율적인 구조를 가지고 있다.

Linke List

하지만 연결 리스트는 구성 아이템들을 자주 추가, 삭제해줘야 할 때 효율적으로 활용이 가능하다. 또한 몇 개의 아이템이 이 데이터 세트에 들어갈지 모를 때에도 유용하다.

 

정리

연결리스트(Linked List) 배열(Array)
노드(node)들 간의 논리적인 순서에 대한 정보만 가짐 논리적 저장순서 = 물리적 저장 순서
사이즈 : 동적
노드가 추가됨에 따라 유연하게 사이즈가 바뀜		 사이즈 : 정적
배열의 크기는 선언 시 지정되어야 함
삽입 : O(n)
(맨 앞, 맨 뒤에만 삽입하면 O(1))		 삽입 : O(n)
삭제한 원소 이후 index의 원소들을 옮겨야함
삭제 : O(n)
(맨 앞, 맨 뒤에서만 삭제하면 O(1))		 삭제 : O(n)
삭제한 원소 이후 index의 원소들을 옮겨야함
검색 : O(n)
순차 접근 방식(처음부터 차례로 검색)		 검색 : O(1)
index알면 바로 원소 접근 가능 (Random Access)
메모리 : 동적 메모리 할당
노드 추가 시 Runtime에 할당, Heap영역에 메모리 할당		 메모리 : 정적 메모리 할당
선언되자 마자 Compile time에 할당, Stack영역에 메모리 할당

 

지금까지 설명해온 연결 리스트는 단일 연결 리스트(Singly-Linked List)였다.

연결 리스트에는 단일 리스트뿐만 아니라 이중 연결 리스트(Doubly-Linked List) 같은 더 다양한 형태도 존재한다.

단일 연결 리스트는 다음 노드의 정보(node)만 알고 있는 한 방향으로 연결된 구조인 반면, 이중 연결 리스트는 각 노드가 이전 정보(previous)와 다음 정보(next)를 모두 가진 양 방향으로 연결된 구조이다.

당연히 양쪽으로 접근이 가능한 이중 연결 리스트가 더 좋은 게 아닐까? 할 수 있지만 더 많은 정보를 가진 만큼 단일 연결 리스트보다 메모리를 더 잡아먹는다는 단점도 분명히 존재한다.

단일 연결 리스트, 이중 연결 리스트 사진

++추가 정리

몇 가지 properties를 알아보기 전에 추가하면 pointer가 한쪽 방향으로만 있는 Linked list를 단일 연결 리스트(singly linked list)라고 하고, pointer가 양쪽 방향으로 왔다 갔다 하는 것을 double Linked List, 첫 번째 노드와 마지막 노드도 연결되어 있어서 순환하게 되어 있는 것은 circular linked list라고 구분한다.

 

singly linked list의 properties를 사진으로 살펴보자.

 

. head : 리스트의 첫 번째 node

. tail : 리스트의 마지막 node

. next : 다음 노드를 가리키는 next pointer tail의 포인터는 Null을 가리킨다.

. length : 리스트에 총 몇 개의 node가 있는지를 나타낸다. 

 

Methods of a Linked List

메서드가 여러 개 있지만 자주 보이는 것들 위주로 정리해보자.

  • . append() : list의 마지막에 추가해준다
  • . prepend() : list의 처음에 넣어준다.
  • . remove(data) : data를 삭제한다.
  • . removeAt(index) : 해당 index에 있는 데이터 node를 삭제한다.
  • . removeHead() : list의 첫 번째 node를 지워주고 그 값을 리턴해준다.
  • . removeTail() : list의 마지막 node를 지워주고 그 값을 리턴해준다.
  • . contains(data) : 전달받은 data가 linked list에 있는지의 여부를 boolean값으로 리턴해준다.
  • . search(data) : data라는 값을 가진 node가 있으면 해당 노드를 리턴해준다
  • . insertAt(data, index) : list의 해당 index자리에 data를 넣어준다.
  • . size : linked list가 가지고 있는 총 데이터 개수를 반환한다.
  • . isEmpty : 데이터의 존재 여부에 따라 Boolean값은 반환한다.

어디서 봤던 코드를 수작업으로 한 번씩 생각해보면서 작성해보았다.

아래 예시는 단일 연결 리스트 코드이다.

class Node{
  constructor(element){
    this.element = element;
    this.next = null;
  }
}
class LinkedList{
  constructor(){
    this.head = new Node("head");
  }
    find(item){
      let currNode = this.head;
      while(currNode.element != item){
        currNode = currNode.next;
      }
      return currNode;
    }
    insert(newElement, item){
      let newNode = new Node(newElement);
      let current = this.find(item);
      newNode.next = current.next;
      current.next = newNode;
    }
    display(){
      let currNode = this.head;
      while(!(currNode.next == null)){
        console.log(currNode.next.element);
        currNode = currNode.next;
      }
    }
    findPrevious(item){
      let currNode = this.head;
      //다음 노드가 존재하면서 다음노드의 아이템이 
      while(!(currNode.next == null) && (currNode.next.element != item)){
        currNode = currNode.next;
      }
      return currNode;
    }
    remove(item){
      let prevNode = this.findPrevious(item);
      if(!(prevNode.next == null)){
        prevNode.next = prevNode.next.next;
      }
    }
}
 
const ll = new LinkedList();
ll.insert("Seoul","head");// head->Seoul
ll.insert("Busan","Seoul");// head->Seoul->Busan
ll.insert("Daegu","Seoul");// head->Seoul->Daegu->Busan
ll.insert("Incheon","Busan");// head->Seoul->Daegu->Busan->Incheon
ll.display();// head->Seoul->Daegu->Busan->Incheon
ll.remove("Busan");
ll.display();// head->Seoul->Daegu->Incheon

아래 예시는 이중 연결 리스트 코드이다.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.previous = null;
  }
}
class LinkedList {
  constructor() {
    this.first = null; 
    this.last = null; 
    this.size = 0; // 연결 리스트의 사이즈로 노드의 개수를 의미합니다.
  }
  /**
 * 전체 노드를 undefined 이외의 값이 나올 때까지 순회하고 값을 찾으면 리턴합니다. 
 * 콜백 함수는 현재 노드와 인덱스를 확인하고 값 또는 undefined를 리턴합니다.
 */
find(callback) {
  for (let current = this.first, position = 0; current; current = current.next, position += 1) {
    const result = callback(current, position);
    if (result !== undefined) { return result; }
  }
  
  return undefined;
}
get(index = 0) {
  return this.find((current , position) => {
    if (position === index) { return current; }
  
    return undefined;
  });
}
indexOf(value) {  
  return this.find((current, position) => {
    if (current.value === value) { return current; }
  
    return undefined
  });
}
addFirst(value) {
  const newNode = new Node(value);
  newNode.next = this.first;
  
  if (this.first) {
    this.first.previous = newNode;
  } else {
    this.last = newNode; // 리스트에 아무 것도 없는 경우입니다.
  }
  this.first = newNode;
  this.size += 1;
  return newNode;
}
addLast(value) {
  const newNode = new Node(value);
  
  newNode.previous = this.last;
  if (this.last) {
    this.last.next = newNode;
  } else {
    this.first = newNode;
  }
  
  this.last = newNode;
  this.size += 1;
  return newNode;
}
add(value, position = 0) {
  if (position === 0) {
    return this.addFirst(value);
  }
  if (position === this.size) {
    return this.addLast(value);
  }
  const current = this.get(position);
  
  if (current) { 
    const newNode = new Node(value);
    newNode.previous = current.previous;
    newNode.next = current;
    current.previous = newNode;
    current.previous.next = newNode;
    this.size += 1;
    return newNode;
  }
  return undefined;
}
}

 

'Base > 자료 구조' 카테고리의 다른 글

Data Structure(4) Heap(힙)  (0) 2021.10.12
Data Structure(3) Graph(그래프)  (0) 2021.09.27
Data Structure(1) Stack (스택), Queue (큐)  (0) 2021.03.08
'Base/자료 구조' Related Articles more
Comments