링크드리스트(연결 리스트)와 배열

1. 연결 리스트

연결 리스트는 선형적인 데이터 구조라는 점에서 배열과 유사하다. 하지만 배열과 달리, 연결 리스트의 요소(elements)들은 특정 메모리 주소나 인덱스에 저장되지 않는다. 오히려 각 요소는 포인터 또는 다음 객체에 대한 링크를 가지고 독립적인 개체에 가깝다.

 

연결 리스트의 각 요소를 노드(node)라 부른다. 노드는 일반적으로 데이터 그리고 다음 노드를 가리키는 링크, 이 2가지 아이템으로 구성된다. 참고로 데이터의 유형은 다양하게 올 수 있다. 

연결 리스트의 가장 첫 번째 지점을 헤드(head)라 부른다. 헤드는 연결 리스트의 첫번째 노드를 의미한다. 마지막 노드는 null을 가리킨다.

만약 연결 리스트가 비어있는 경우, 헤드는 null을 참조하게 된다.

 

자바스크립트로 연결 리스트를 표현하자면 아래와 같이 표현이 된다.

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

1-1. 연결 리스트의 장점

연결 리스트는 데이터 구조의 큰 틀을 바꾸지 않고 노드를 추가하거나 삭제하기 쉽다는 장점을 가지고 있다.

이러한 점에서 배열과 대비가 된다.

 

1-2. 연결 리스트의 단점

연결 리스트는 탐색이 느리다. 배열과 달리, 연결 리스트는 데이터에 무작위 접근(random access)을 할 수 없기 때문이다.

노드들은 첫 번째 노드부터 순차적으로만 접근해야 한다.

 

연결 리스트는 배열보다 더 많은 메모리를 사용한다. 왜냐하면 각 노드는 포인터를 담고 있기 때문이다.

 

1-3. 연결 리스트의 유형

연결 리스트는 크게 3가지 유형이 있다.

1. 단일 연결 리스트(Singly Linked Lists) : 각 노드는 하나의 포인터만 가진다. 우리가 위에서 이야기한 유형이 단일 연결 리스트이다.

2. 이중 연결 리스트(Doubly Linked Lists) : 각 노드는 2개의 포인터를 가지는데, 하나는 다음 노드, 나머지는 이전 노드를 가리킨다.

3. 원형 연결 리스트(Circular Linked Lists) : 연결 리스트를 응용한 유형으로, 마지막 노드의 포인터가 첫 노드 또는 특정 노드를 가리키고 있는 마치 루프 형태를 가지는 유형을 말한다.

 

1-4. 연결 리스트 메소드

1. size()

2. clear()

3. getLast()

4. getFirst()

 

1. size()

size() 메소드는 연결 리스트에 있는 노드들의 개수를 반환

size() {
    let count = 0; 
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
}

2. clear()

clear() 메소드는 리스트를 비우는 역할

clear() {
    this.head = null;
}

3. getLast()

getLast() 메소드는 연결 리스트의 마지막 노드를 반환

getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}

4. getFirst()

getFirst() 메소드는 연결 리스트의 첫 번째 노드를 반환

getFirst() {
    return this.head;
}

 

2. 배열

배열은 연관된 데이터를 모아서 관리하기 위해서 사용되는 데이터 타입이다. 변수가 하나의 데이터를 저장하기 위한 것이면 배열은 여러 개의 데이터를 저장하기 위한 것이라고 할 수 있다.

 

인덱스와 값으로 이뤄지는데 인덱스(index)는 어떤 값에 접근하기 위해 필요한 것이다.

값(value)는 배열 안에 실제로 들어가 있는 값이다.

ex) Week[7] = {월, 화, 수, 목, 금, 토, 일} 이라는 배열이 있다고 가정하자. 요일은 배열의 값이 되고, '수' 라는 값에 접근하고 싶으면 인덱스 n 를 통해 접근 할 수 있다.

아래 그림을 참고하자.

배열은 값에 접근할 때 O(1)의 시간 복잡도를 갖는다. 즉, 배열은 어떤 값에 접근하던지 모두 동일한 시간이 걸린다. 

배열의 중간에 요소를 삽입 혹은 삭제를 할 경우, 시간 복잡도는 O(n)이 될 수 있다. 이는 중간의 요소를 추가하거나 삭제를 할 때 나머지 요소들의 위치를 조정해야 하기 때문이다.

 

이 아래는 C언어 한정이다. 포인터 연산

배열이 인덱스를 참조하여 값을 접근하는 방식은 배열의 처음 주소를 기준으로 (데이터형의 크기) * (인덱스) 만큼 주소를 건너뛰어서 그 값을 전달 해준다. 그렇기 때문에 배열의 접근은 꼭 week[2]로 접근 하는 것이 아니라 (week + 2)와 같은 방식으로 접근할 수 있다.

2-1. 배열의 장점

접근이 빠르고, 간단하다.

n번째 인덱스에 접근할 경우 arr[n]을 사용하면 빠른 시간에 접을 할 수 있다.

 

2-2. 배열의 단점

배열을 사용하기 위해서는 처음에 배열의 크기를 선언해야 하고, 크기의 수정이 불가능하다. 그래서 메모리 사용이 비효율적이다.

또한 중간 데이터를 삭제 했을 때 빈 배열을 처리하는 것이 매우 번거롭다.