24.05.31 배열과 연결 리스트(NodeList)

배열이란?

배열이란 여러 연관된 데이터를 모아 관리하기 위한 데이터 타입이다. 배열은 크기를 미리 정해놓아야 하여 정적 자료구조로 분류된다. 내부 요소들은 메모리 상에 연속적으로 저장되며 연속된 메모리 주소를 할당 받게 된다.. 이러한 특성때문에 배열의 요소에 빠르게 접근할 수 있다.

배열의 데이터 저장과 연속적으로 저장되는 모습

 연속된 메모리 주소를 할당 받기 때문에 우리가 이미 알고있는 인덱스(index)를 갖게 된다. 배열의 특정 위치 값을 찾기 위해 array[0]으로 접근할 때 대괄호 안의 숫자가 인덱스이다. 또한 인덱스를 갖기 때문에 임의 접근이 가능하여 접근과 탐색에 용이하다.

 하지만 배열의 크기가 고정되어 있어, 배열의 크기보다 더 많은 데이터를 저장할 수 없다. 

 

연결리스트란?

연결리스트(Linked List)란 데이터를 효과적으로 저장하고 관리하기 위한 자료구조이다. 배열이 연속된 메모리 공간에 데이터를 저장하는 것과 달리, 연결리스트는 떨어진 메모리 공간에 존재하는 노드들을 포인터로 연결하여 데이터를 저장한다. 배열과 달리 크기를 정할 필요가 없어 동적 자료구조로 분류된다.

 배열과 달리 크기를 정해놓지 않아 제한이 없고, 그러므로 데이터 추가, 삭제가 자유롭다. 

노드에 데이터가 저장되고 포인터가 다음 노드를 가리키는 모습

연결리스트의 단점은 탐색이 배열에 비해 느리다는 점이다. 그 이유는 무작위 접근이 불가하고 첫번째 노드부터 순차적으로 접근해야하기 때문이다. 또한 각 노드가 포인터를 포함하고 있기 때문에 배열보다 더 많은 메모리를 사용한다.

 

위 그림은 단일 연결리스트를 표현한 그림이다. 단일 연결리스트란 각 노드가 하나의 포인터만 가지는 것이다.

다른 예로 이중 연결리스트와 원형 연결리스트가 있다. 이중 연결리스트는 각 노드가 2개의 포인터를 가져 해당 노드의 다음 노드와 이전 노드를 가리킨다. 원형 연결리스트는 마지막 노드의 포인터가 첫 노드나 특정 노드를 가리키는 루프형태의 노드를 의미한다.

 

연결리스트는 음악을 들을 때 순서에 따라 이전 곡과 다음 곡이 연결되어있는데 이럴 때 많이 사용된다고 한다. 또, 각종 편집 프로그램의 history같은 이전 행동의 내역을 확인하거나 되돌리는데에도 연결리스트가 사용된다.

 

연결리스트의 각 요소를 노드(node), 가장 첫번째 지점을 헤드(head)라고 하며, 마지막 노드는 null을 가리킨다. 만약 연결리스트가 비어있는 경우 헤드는 null값을 참조한다.

 

다음은 js에서 리스트노드를 만들어본 예시이다.

//nodetest.js
class ListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
class NodeList {
    constructor(head = null) {
        this.head = head;
    }
}

let node1 = new ListNode('아이유 - Celebrity');
let node2 = new ListNode('10cm - 폰서트');
node1.next = node2;
let list = new NodeList(node1);

console.log(list);

 

console.log(list) 결과

 

 

 

 

 

---

 

자바스크립트로 연결 리스트를 구현하는 방법

 

[개념 콕] 웹 개발 지식 편 | 배열(Array)과 연결 리스트(Linked List) - 내일배움캠프 블로그

 

간략 설명! 배열(Array)과 연결 리스트(Linked List)에 대해서 알아보자! - 차이점과 시간복잡도, 활용