[Algorithm] Linked List (연결 리스트)

안자매 2022. 6. 22.

개인적으로 공부하면서 기록하는 공간으로
잘못된 정보는 댓글을 통해 알려주시면 감사하겠습니다 :-)

▪ ▪ ▪ ▪ ▪

연결 리스트

연결 리스트는 리스트의 항목들을 노드에 분산하여 저장하는 리스트이다.

노드의 구성

- 데이터 필드 (Data Field): 리스트의 원소, 즉 데이터 값을 저장하는 곳

- 링크 필드 (Link Field): 다른 노드의 주소값을 저장하는 곳

👉🏻 연결 리스트는 일반 배열과 달리 데이터 뿐 아니라 다음 데이터를 가르키는 주소를 함께 가지고 있다.

연결리스트는 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요 없고 크기 제한이 없다는 장점이 있는 반면, 구현이 어렵고 까다로우며 오류가 발생하기 쉽다는 단점이 있다.

연결리스트의 종류

1) 단일 연결 리스트 (Simple Linked List)

2) 이중 연결 리스트 (Doubly Linked List)

3) 원형 연결 리스트 (Curcular Linked List)

단일 연결 리스트 (Simple Linked List)

단일 연결 리스트는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용해 연결한다. 이 때 마지막 노드의 링크 값은 NULL을 가리켜야 한다.

이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트이다.

원형 연결 리스트 (Curcular Linked List)

원형 연결 리스트는 일반적인 연결 리스트의 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

구현하기

1. 기본 구조

// 단일 연결 리스트
class Node {
	constructor(data, next=null) {
        this.data = data;
    	this.next = next;
    }
}

// 이중 연결 리스트
class Node {
	constructor(prev=null, data, next=null) {
        this.prev = prev;
        this.data = data;
    	this.next = next;
    }
}

연결의 핵심은 Node이며, Node는 Data Field와 Linked Field로 구성되어 있다.

단일 연결 리스트의 경우 뒤 노드의 값을 가리키는 next와 자신이 가지는 값인 data로 구성되어 있고,

이중 연결 리스트의 경우 자신의 앞 노드를 가리키는 prev가 추가된다.

class LinkedList {
	constructor() {
    	this.head = null;
        this.count = 0;
    }
}

처음에 데이터가 없다면 head는 null 이고, 리스트의 원소의 개수를 찾기 위해 count를 사용하며 default는 0으로 한다.

2. 연결리스트에 새로운 노드 추가

① 맨 앞에 추가

insertFirst(data) {
	this.head = new Node(data, this.head);
    this.size++;
}

연결 리스트의 맨 앞에 노드를 추가할 때는 head에 새로운 node가 들어가게 되고, 기존의 head는 next로 밀려나게 된다.

② 중간에 추가

insertAt(prev, data) {
	const node = new Node(data);
    let currentNode = this.head;
    
    while (currentNode.data !== prev) {
    	currentNode = currentNode.next;
	}
    
    let temp = currentNode.next;
    node.next = temp;
    currentNode.next = node;
    
    this.count++;
}

연결 리스트의 중간에 노드를 추가할 때는 새로운 node의 next가 prev의 next를 가리키게 한 다음, while문으로 찾아낸 prev의 next가 다시 새로운 노드를 가리키도록 바꿔준다.

③ 맨 뒤에 추가

insertLast(data) {
    let node = new Node(data);
    let current;

    if (!this.head) {
      this.head = node;
    } else {
      current = this.head;

      while (current.next) { 
        current = current.next; 
      }

      current.next = node; 
    }
    this.size++; 
  }

3. 연결리스트에 노드 삭제

removeAt(index) {
    let current = this.head;
    if (current.data === data) {
    	temp = current.next;
        current.next = null; 
        this.head = temp;
    } else {
        while (current.next.data !== data) {
    		current = current.next;
    	}
    
        temp = current.next.next;
        current.next.next = null; 
        current.next = temp;
    }
    this.count--;
  }