[자료구조] 배열과 연결리스트

 

컴퓨터 공학 관련 수업을 수강한 사람들이라면 자료구조에 대해서는 익히 들어봤을것이다.

그중에서 배열(Array)과 연결리스트(Linked List)는 둘다 선형 데이터 구조이고, 데이터를 순차적으로 저장하고 관리한다는 측면에서는 공통적이지만, 메모리 할당과 시간 복잡도, 용도 측면에서 많은 차이점이 있다.

 

배열

• 메모리할당: 배열은 우리 모두가 알다시피 연속적인 위치에 데이터를 저장한다. 배열은 인덱스를 통해 데이터에 빠르게 접근할 수 있지만, 배열의 크기를 미리 정해야 하고, 배열을 확장하거나 축소하는 것이 번거로울 수 있다.
• 시간복잡도: 인덱스를 통해 접근하면 O(1)의 시간 복잡도를 가진다. 하지만, 배열의 시작이나 중간에 요소를 삽입하거나 삭제해야할 경우, O(n)의 시간 복잡도가 소요된다. 
• 특징: 자바스크립트를 제외한 대부분의 프로그래밍 언어에서는 하나의 배열에 하나의 데이터 타입만 저장할 수 있다. 이는 데이터 타입에 따라 저장 공간의 차이가 있기 때문이며, 배열은 연속적인 주소상의 데이터를 저장하는데 이때 더 큰 데이터 타입의 데이터가 들어오면 문제가 될 수 있다고 한다. 

배열 예제 코드

let array = [1, 2, 3, 4, 5];
console.log(array[2]); // 접근 - O(1)

// 중간에 요소 삽입 - O(n)
array.splice(2, 0, 6);
console.log(array);

// 요소 삭제 - O(n)
array.splice(2, 1);
console.log(array);

 

연결리스트

• 메모리할당: 연결 리스트는 각 요소(노드)가 데이터와 다음 노드를 가리키는 포인터를 포함한다. 요소들은 메모리상에서 연속적일 필요가 없어 동적으로 크기가 조정된다.
• 시간복잡도: 연결 리스트는 특정 요소에 접근할 때 처음부터 리스트를 순회해야 하므로 O(n)의 시간이 걸린다. 그러나 삽입과 삭제는 해당 노드에 접근하면 O(1)의 시간으로 처리할 수 있다.

연결리스트 예제 코드

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

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

    // 요소 추가 - O(1) or O(n), 위치에 따라 다름
    addAtFront(data) {
        let newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    // 요소 추가 - O(n)
    addAtEnd(data) {
        let newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let last = this.head;
        while (last.next) {
            last = last.next;
        }
        last.next = newNode;
    }

    // 리스트 출력 - O(n)
    printList() {
        let temp = this.head;
        while (temp) {
            console.log(temp.data);
            temp = temp.next;
        }
    }
}

let list = new LinkedList();
list.addAtFront(1);
list.addAtEnd(2);
list.addAtFront(3);
list.printList();  // 3 -> 1 -> 2