배열 vs 리스트 vs 연결 리스트

 

선형구조

 - 자료를 순차적으로 나열한 형태

 - 배열, 연결 리스트, 스택, 큐

 

비선형 구조

 - 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

 - 트리, 그래프

 

 

배열(Array)

 - 메모리를 연속적으로 미리 선언하고 사용함.

 - 중간 요소를 삭제할 경우, 해당 부분은 메모리를 돌려받지 않고 놔둠.

 

 - 장점 : 메모리 주소가 연속적이다. 접근 빠름.

 - 단점 : 배열의 크기를 변경할 수 없다.

 

 

동적 배열(ArrayList)

 - 연속된 메모리 공간을 사용한다.

 - 배열의 크기를 유동적으로 조정 가능하다.

 - 저장 가능한 메모리 용량(Capacity)과 현재 사용 중인 공간의 크기(Size)가 있으며,

   현재 가용량(Capacity)을 넘어갈 때 더 큰 공간의 메모리를 할당함.

   (전체 이동할 때 비용이 크기 때문에, 여유분을 잡아놓는다.) 

 

 - 장점 : 유동적인 배열 크기. 메모리 주소가 연속적이다. 접근 빠름.

 - 단점 : 추가/삭제할 경우 뒤쪽 메모리들을 이동시켜 연속이 되도록 채워 넣어야 하기 때문에 비용이 크다.

            다음 데이터를 가리키기 위한 추가 메모리 공간 필요.

class MyList<T>
{
    const int DEFAULT_SIZE = 0;
    T[] _data = new T[DEFAULT_SIZE];

    public int Count { get; set; }
    public int Capacity => _data.Length;

    // O(1)
    public void Add(T item)
    {
        if(Count >= Capacity)
        {
            T[] newArray = new T[Count * 2];
            for (int i = 0; i < Count; i++)
                newArray[i] = _data[i];

            _data = newArray;
        }

        _data[Count] = item;
        Count++;
    }

    // O(1) 
    public T this[int index]
    {
        get => _data[index];
        set{ _data[index] = value; }
    }

    // O(N)
    public void RemoveAt(int index)
    {
        for (int i = index; i < Count - 1; i++)
            _data[i] = _data[Count - 1];

        _data[Count - 1] = default;
        Count--;
    }
}

 

연결 리스트(LinkedList)

 - 노드마다 다음 노드의 주소를 가지고 있다.

 - 연결되지 않은 메모리를 사용한다.

 

 - 장점 : 추가, 삭제 비용이 적다. (메모리 주소만 고쳐 써주면 된다)

 - 단점 : 탐색을 할 때 비용이 높아진다.

            랜덤 액세스(N번째 요소에 접근)하려면 앞에서부터 순서대로 찾아야 한다.

class Node<T>
{
    public T Data;
    public Node<T> Next { get; set; }
    public Node<T> Prev { get; set; }
}

// 대략적인 구현. 실제는 AddFirst, AddAfter, AddBefore등 더 많은 함수가있다.
class MyLinkedList<T>
{
    public Node<T> Head = null;
    public Node<T> Tail = null;
    public int Count { get; set; }

    public Node<T> AddLast(T data)
    {
        Node<T> newNode = new Node<T>();
        newNode.Data = data;

        if (Head == null)
            Head = newNode;

        if (Tail != null)
        {
            Tail.Next = newNode;
            newNode.Prev = Tail;
        }

        Tail = newNode;
        Count++;
        return newNode;
    }

    public void Remove(Node<T> node)
    {
        if (Head == node)
            Head = Head.Next;

        if (Tail == node)
            Tail = Tail.Prev;

        if (node.Prev != null)
            node.Prev.Next = node.Next;

        if (node.Next != null)
            node.Next.Prev = node.Prev;

        Count--;
    }
}