[자료구조] 동적배열, 연결리스트 구현 및 시간복잡도

동적배열 List

Add - O(1)

RemoveAt - O(N)

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

        public int Count;// 실제 사용데이터
        public int Capacity { get { return _data.Length; } }// 예약한 데이터 개수

        //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(1)
        public T this[int index]
        {
            get { return _data[index]; }
            set { _data[index] = value; }
        }

        //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--;
        }
    }

연결List

연결리스트는 인덱스접근을 제공하지 않는다.

Add - O(1)

Remove - O(1)

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

    class MyLinkedList<T>
    {
        public MyLinkedListNode<T> Head = null;//첫번째
        public MyLinkedListNode<T> Tail = null;//마지막
        public int Count = 0;

        public MyLinkedListNode<T> AddLast(T data)
        {
            MyLinkedListNode<T> newRoom = new MyLinkedListNode<T>();
            newRoom.Data = data;

            //만약 방이 아직 없다면. 새로 추가한 첫 번째 방이 곧 head이다.
            if (Head == null)
                Head = newRoom;
        
            //기존의 마지막방과 새로 추가된 방을 연결.
            if(Tail != null)
            {
                Tail.Next = newRoom;
                newRoom.Prev = Tail;
            }

            //새로추가되는 방을 마지막방으로 등록
            Tail = newRoom;
            Count++;

            return newRoom;
        }
        public void Remove(MyLinkedListNode<T> room)
        {
            //기존의 첫번째 방의 다음 방을 첫 번째 방으로 변경.
            if (Head == room)
                Head = Head.Next;

            //기존의 마지막 방의 이전방을 마지막 방으로 변경.
            if (Tail == room)
                Tail = Tail.Prev;

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

            if(room.Next != null)
                room.Next.Prev = room.Prev;
        }
    }