[알고리즘] 배열, 동적 배열, 연결 리스트

배열

• 크기가 고정적이며 변경할 수 없다.
• 요소들이 메모리상에 연속적으로 저장된다.

문제점

• 유동적으로 사용할 수 없다.

 

동적 배열

• 크기가 유동적이다.
• 요소들이 메모리상에 연속적으로 저장된다. 

문제점

• 크기가 변경될 때 많은 비용이 발생한다.
• 삽입, 삭제가 어렵다.

해결책

• 배열이 생성될 때 지정한 크기보다 1.5~2배 정도 더 많은 공간을 미리 차지해둔다.

간단 구현

class MyList<T>
{
    const int DEFAULT_SIZE = 1;
    T[] data = new T[DEFAULT_SIZE];

    public int Count = 0; //실제로 사용되는 공간 개수
    public int Capacity { get { return data.Length; } } //예비 공간 개수

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

    // O(1)
    public void Add(T item)
    {
        // 1. 공간이 남아있는지 확인
        // 특수한 상황에서만 실행되므로 시간복잡도 무시
        if(Count >= Capacity)
        {
            // 공간 확보
            T[] newArray = new T[Count * 2];
            for(int i = 0; i < Count; i++)
                newArray[i] = data[i];
            data = newArray;    
        }

        // 2. 데이터 삽입
        data[Count] = item;
        Count++;
    }

    // O(n)
    public void RemoveAt(int index)
    {
        for(int i = index; i < Count - 1; i++)
            data[i] = data[i + 1];
        data[Count - 1] = default(T);

        Count--;
    }
}

 

연결 리스트

• 요소들이 메모리상에 연속적으로 저장되지 않는다.
•  삽입, 삭제가 유리하다.

문제점

• 인덱서를 사용할 수 없다.
• 탐색에 비교적 많은 비용이 든다.

간단 구현

class MyLinkedListNode<T>
{
    public T Data;
    public MyLinkedListNode<T> Next;
    public MyLinkedListNode<T> Prev;
}

class MyLinkedList<T>
{
    public int Count;
    public MyLinkedListNode<T> First = null;
    public MyLinkedListNode<T> Last = null;

    // O(1)
    public MyLinkedListNode<T> AddLast(T data)
    {
        MyLinkedListNode<T> newNode = new MyLinkedListNode<T>();
        newNode.Data = data;

        if(First == null)
            First = newNode;

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

        Last = newNode;
        Count++;

        return newNode;
    }

    // O(1)
    public void Remove(MyLinkedListNode<T> node)
    {
        if(First == node)
            First = First.Next;

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

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

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

        Count--;
    }
}