[자료구조] 리스트 VS 연결 리스트(LIST VS LinkedList)

일단 여기서 '리스트'는 전형적인 '선형 리스트'를 의미한다고 보면 된다.

 

우선 면접에서 이런 질문을 던진다면... 난 이 답변부터 이야기하겠다.

 

선형 리스트는 ‘순차적으로’ 구현한 것이기에(연속된 메모리) 결과론적으로 Random Access(임의 접근)이 가능해지게 되므로 상대적으로 접근과 탐색에 강점을 가지게 된다.

 

연결 리스트는 연속된 메모리 공간에 저장할 필요가 없는 특성상 임의 접근이 불가능하며, 그 대신 저장 공간의 활용이 상당히 자유로워지게 되는 것이다.

 

이제 둘을 시간복잡도 관련 관점으로 한번 비교해보자.

 

연결 리스트 예제

using System;

class Node<T>
{
    public T Data;
    public Node<T> Next;

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

class LinkedList<T>
{
    private Node<T> head;

    public LinkedList()
    {
        head = null;
    }

    // 연결 리스트에 항목 추가
    public void Add(T data)
    {
        Node<T> newNode = new Node<T>(data);
        if (head == null)
        {
            head = newNode;
        }
        else
        {
            Node<T> current = head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

    // 연결 리스트에서 항목 탐색
    public bool Search(T data)
    {
        Node<T> current = head;
        while (current != null)
        {
            if (current.Data.Equals(data))
            {
                return true;
            }
            current = current.Next;
        }
        return false;
    }
}

단순 선형 리스트 예제

using System;

public class Node<T>
{
    public T Data;
    public Node<T> Next;

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

public class SinglyLinkedList<T>
{
    private Node<T> head;

    public SinglyLinkedList()
    {
        head = null;
    }

    // 리스트에 항목 추가
    public void Add(T data)
    {
        Node<T> newNode = new Node<T>(data);
        if (head == null)
        {
            head = newNode;
        }
        else
        {
            Node<T> current = head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

    // 리스트에서 항목 탐색
    public bool Search(T data)
    {
        Node<T> current = head;
        while (current != null)
        {
            if (current.Data.Equals(data))
            {
                return true;
            }
            current = current.Next;
        }
        return false;
    }
}

코드리뷰가 끝났다면 다음과 같은 관점으로 분석해보자.

 

2. 탐색(Search)의 경우          

 

상기 코드를 보면 0번째 인덱스부터 마지막 인덱스까지 접근하면서 원하는 데이터를 찾아야 하는데, 찾으려는 데이터가 없거나 마지막 노드면(최악의 경우) 결과적으로 N개의 데이터를 살펴봐야 한다. 따라서 연결 리스트의 시간 복잡도는 O(n)!

 

선형 리스트의 경우도 하나하나 비교해야하는 만큼 시간 복잡도는 같다.

하지만 만약 선형 리스트가 정렬(sort) 되어있는 경우 Binary Search(이진 탐색)이 가능해지게 되어, 이 경우에는 O(logn)이다.

 

이 치명적인 단점 때문에 연결 리스트 단독으로 사용하기보다 실제 현업에는B+트리 자료구조를 훨씬 더 많이 사용한다.

 

3. 읽기(Read)의 경우

 

앞서 언급했듯이 임의 접근이 불가능한 연결 리스트 특성상 읽기가 쥐약이다.

우선 선형 리스트는 그냥 임의 접근이 가능하므로 시간복잡도는 그냥 O(1).

연결 리스트는 하나하나 원소를 비교해야 하므로 최악의 경우에는 O(n)이다.

 

4. 삽입/삭제(Insert/Delete)의 경우

 

둘이 어느 정도 비슷하다. 찾아야 할 데이터가 중간에 있으면 얄짤없이 O(n).

 

다만 세부적인 부분에서는 좀 달라지는데, 단순 리스트는 맨 끝이라면 O(1)이지만 찾아야 할 데이터가 처음이나 중간이라면 그 인덱스까지 이동해야 하므로 O(n)인 것.

또한 연결 리스트는 만약 찾아야 할 노드의 위치를 정확히 알고 있다는 가정 하에 O(1)을 가진다.

 

5. 메모리적인 관점에서

 

선형 리스트는 서로 독립되어 있는 노드다. 하지만 연결 리스트는 특성상 일반적으로 다음/이전 노드에 대한 포인터를 위한 공간이 추가적으로 더 필요할 수 밖에 없다. 따라서 기억 공간 효율이 좋지 않다... 라고 할 수 있음.

어디까지나 컴퓨터수학적인 개념인 빅오 표기법으로 이야기를 한 것이지, 실제 퍼포먼스는 거의 모든 환경에서 List가 LinkedList보다 퍼포먼스가 더 뛰어나다.

 

앞서 언급했듯이 LinkedList는 리스트 중간에 요소를 삽입하거나 제거할 때 강점을 지니고 List는 리스트 끝에 요소를 추가할 때 강점을 지닌다. 일반적으로 전자의 경우는 잘 없으니까..

 

그리고 역시 Random Access의 부재로 인한 읽기 퍼포먼스 저하도 영향이 크다.

연결 리스트의 무작위 액세스는 결국 매번 체인을 따라 이동해야 하다 보니 비용이 꽤 든다.

 

또 하나는 마이크로프로세서가 메모리 캐싱을 구현하는 방법과 관련이 있다. 

참조 지역성(locality of reference)과 관련된 개념 때문이다.

 

학부에서 우리가 배울 내용과 크게 관련이 있는 것은 아니니 궁금한 사람만 들어가서 읽어보는 것이 좋다.

 

Number crunching: Why you should never, ever, EVER use linked-list in your code again - 링크

 

시간 복잡도로 표를 만들어 둘의 차이점을 풀이해보자.

 

	List	LinkedList
읽기	O(1)	O(n)
탐색	O(n) / O(logn)	O(n)
삽입/삭제	O(n) 맨 뒤 요소 변경 - O(1)	O(n) 찾아야 할 노드 위치를 알고 있으면 - O(1)
메모리	상대적으로 적음	상대적으로 많음

 

추가적으로 관심이 있는 사람들은 여기서 실제 테스트를 돌려보면 된다.