Linked List

연결 리스트(Linked List)란?

• Linked List란 배열과 마찬가지인 선형 데이터 구조이다.
• 배열과 다르게 Linked List는 인접한 위치에 저장되지 않는다.
• 각 요소를 노드라고 부른다.

---

Linked List의 구조

기본적으로 Linked List는 아래 그림의 구조를 가지고 있다.

Linked List의 구조

연속적이지 않은 메모리 공간에 데이터를 저장하며 각 데이터는 포인터로 연결되어 있다.

---

Array 대신 Linked List를 사용하는 이유

• 배열은 Linked List와 같은 선형 데이터 구조이지만 제한이 있다.
• 배열의 크기는 고정되어 있기 때문에 사용량에 관계없이 메모리가 배열의 크기만큼 할당된다.
• 예를 들어, 크기가 5인 배열이 있을때 3번째 까지만 사용해도 메모리에는 5만큼 할당된다.
• javascript에서는 상관없다. 어차피 사용하는 만큼 할당되기 때문이다.
• 배열에 새로운 데이터를 삽입하는것은 비용이 많이 든다.

때문에 Linked List를 사용하는 가장 큰 이유는 1. 동적 크기를 가지고 있고, 2. 삭제/삽입이 용이하기 때문이다.

---

단점

하지만 Linked List도 단점이 존재한다.

• 먼저 임의 엑세스가 불가능하다. 첫번째 노드부터 순차적으로 요소에 엑세스해야한다. -> 특정 요소를 검색할 때 비효율적이다.
• Linked List의 각 요소에는 Next를 가르키는 포인터가 필요하기 때문에, 추가적인 메모리 공간이 필요하다.

---

Linked List 생성

추가하자면, pointer가 한쪽 방향으로만 있는 Linked list를 singly linked list라고 하고 pointer가 양쪽 방향을 가르키는 것을 doubly linked list, 첫번째 노드와 마지막 노드도 연결되어서 순환하는 것은 circular linked list라고 한다.

아래 예제는 js에서의 singly linked list의 구현방법이다.

• Linked List의 첫번째 노드는 head라고 부른다
• Linked List의 마지막 노드는 tail이라고 부른다
• singly linked list의 tail의 포인터는 null이다.

// Linked list 노드 생성자 클래스
let head;
class Node {
  constructor(d) {
    // 실제로 객체안에 들어있는 데이터
      this.data = d;
    // 포인터
      this.next = null;
  }
}

  head = new Node(1);    // 첫번째 head
  const second = new Node(2);
  const third = new Node(3);

/*
  현재 각 노드들의 상태

  llist.head        second              third
      |                |                  |
      |                |                  |
  +----+------+     +----+------+     +----+------+
  | 1  | null |     | 2  | null |     |  3 | null |
  +----+------+     +----+------+     +----+------+ 
*/

  head.next = second; // 첫번째 node인 head의 포인터를 second 노드로 연결

/*  
  현재 각 노드들의 상태

  llist.head        second              third
      |                |                  |
      |                |                  |
  +----+------+     +----+------+     +----+------+
  | 1  |  o-------->| 2  | null |     |  3 | null |
  +----+------+     +----+------+     +----+------+ 
*/

  second.next = third; // 두번째 node인 second의 포인터를 third 노드로 연결

/*  
  현재 각 노드들의 상태

  llist.head        second              third
      |                |                  |
      |                |                  |
  +----+------+     +----+------+     +----+------+
  | 1  |  o-------->| 2  |  o-------->|  3 | null |
  +----+------+     +----+------+     +----+------+ 
*/

// 각 노드를 순차적으로 출력하는 함수
const printList = () => {
    let node = head;
    while (node != null) {
      console.log(`data: ${node.data}, next: ${node.next}`);
      node = node.next;
    }
}

printList();

/*
    결과
    data: 1, next: [object Object]
    data: 2, next: [object Object]
    data: 3, next: null
    * [object Object]로 나오는 이유 next가 object 전체를 가리키고 있기 때문이다.
*/

---

Linked List 의 Node 추가

맨 앞에 노드를 추가하는 방법

노드를 맨 앞에 추가

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

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

const insertFirst = (new_data) => {
    /* 1 & 2: 새로운 노드를 만들고 데이터를 넣는다 */
    const new_node = new Node(new_data);

    /* 3. 새로 만든 노드의 포인터를 기존의 head로 만든다. */
    new_node.next = head;

    /* 4. head를 new_node로 바꾼다. */
    head = new_node;
}
const fourth = insertFirst(4);



const printList = () => { ... }

printList();

/*
    결과
    data: 4, next: [object Object]
    data: 1, next: [object Object]
    data: 2, next: [object Object]
    data: 3, next: null
    * data 4가 첫번쨰 head가 되었다.
*/

중간에 노드를 추가하는 방법

노드를 중간에 추가

...
...
...

const fourth = insertFirst(4);

const insertMiddle = (prev_node , new_data) => {

    /* 1. 이전 노드가 null 이나 undefined 인지 check */
    if (!prev_node) {
        throw new Error('이전 노드가 null 입니다.')
        return;
    }

    /* 2 & 3. 새로운 노드를 생성 후 데이터를 넣는다. */
    const new_node = new Node(new_data);

    /* 4. 새로운 노드의 포인터를 이전 노드의 next로 변경  */
    new_node.next = prev_node.next;

    /* 5. 이전 노드의 포인터를 새로운 노드로 변경 */
    prev_node.next = new_node;
}

// data가 2인 노드 다음에 data가 5인 노드 삽입
const fifth = insertMiddle(second, 5)



const printList = () => { ... }

printList();
/*
    결과
    data: 4, next: [object Object]
    data: 1, next: [object Object]
    data: 2, next: [object Object]
    data: 5, next: [object Object]
    data: 3, next: null

*/

마지막에 노드를 추가하는 방법

노드를 마지막에 추가

...
...
...
const fifth = insertMiddle(second, 5)

const insertLast = (new_data) => {
    /* 1 & 2 & 3. 노드를 만들고 데이터를 추가 한 후, next를 null로 설정한다(tail이기 때문) */
    const new_node = new Node(new_data);

    /* 4. Linked List가 빈 경우 새로운 노드를 헤드로 만든다 */
    if (!head) {
        head = new Node(new_data);
        return;
    }

    /* 5. Else traverse till the last node */
    let last = head;
    while (last.next != null) {
        last = last.next;
    }

    /* 6. 마지막 노드에 추가  */
    last.next = new_node;
    return;
}

const sixth = insertLast(6)


const printList = () => { ... }

printList();


/*
    결과
    data: 4, next: [object Object]
    data: 1, next: [object Object]
    data: 2, next: [object Object]
    data: 5, next: [object Object]
    data: 3, next: [object Object]
    data: 6, next: null

*/

---

Linked List 의 Node 삭제

반복문으로 Node 삭제

삭제할 Node를 temp에 저장하고 연결을 끊어주는 방식

...
...
...

console.log('---------삭제 이전---------')
printList();
/**
 * data: 4, next: [object Object]
 * data: 1, next: [object Object]
 * data: 2, next: [object Object]
 * data: 5, next: [object Object]
 * data: 3, next: [object Object]
 * data: 6, next: null
 */

// data를 받아서 해당하는 data가 들어있는 노드 삭제
const deleteNode = (data) => {
    // temp에 head를 저장하고 이전 노드(prev)를 선언
    let temp = head, prev = null;

    // head 노드 자체가 지워질 경우
    if (temp != null && temp.data === data) {
        head = temp.next; // 헤드를 바꾸고 return
        return;
    }

    // data가 들어있는 삭제될 노드 찾기
    // 찾으면 loop를 빠져나감
    while (temp != null && temp.data !== data) {
        prev = temp;
        temp = temp.next;
    }

    // data가 Linked List안에 없는 경우 retrun
    if (temp == null) {
        return;
    }

    // 이전 노드의 next를 삭제할 노드의 next로 재할당해서 해당 노드를 Linked List에서 삭제
    prev.next = temp.next;
}

deleteNode(2); // data가 2인 노드 삭제


console.log('---------삭제 이후---------')
printList();
/**
 * data: 4, next: [object Object]
 * data: 1, next: [object Object]
 * data: 5, next: [object Object]
 * data: 3, next: [object Object]
 * data: 6, next: null
 */

---

사용된 전체 코드

https://github.com/rkdden/Data-Structure/blob/main/linkedList.js

GitHub - rkdden/Data-Structure

출처

https://www.geeksforgeeks.org/linked-list-set-1-introduction/?ref=lbp

Linked List | Set 1 (Introduction) - GeeksforGeeks

 

잘못된 부분이 있으면 지적은 언제나 환영입니다.