[C#자료구조와알고리즘] 선형자료기초(배열, 연결 리스트)

선형 자료 구조 VS 비선형 구조

선형구조

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

- 종류: 배열, 연결 리스트, 스택/큐

 

비선형 구조

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

- 종류: 트리, 그래프

 

선형 자료 구조

배열

public int[] _data = new int[25];

- 개념: 사용할 방 개수를 고정해서 계약하고 연속된 방으로 배정받아 사용한다.

- 장점: 연속

- 단점: 추가, 제거 불가, 유동적으로 상황에 맞춰서 사용할 수 없다.

 

동적 배열

public List<int> _data2 = new List<int>(); 

- 개념: 사용할 방 개수를 유동적으로 가능, 연속된 방으로 배정받아 사용한다.

- 할당 정책: 실제로 사용할 공간보다 많이, 여유분을 두고 사용한다. 이동 횟수를 최소화한다.

- 장점: 유동적

- 단점: 중간 삽입/삭제

 

연결 리스트

public LinkedList<int> _data3 = new LinkedList<int>(); 

- 개념: 연속되지 않은 공간 사용

- 장점: 중간 추가/삭제 이점

- 단점: n번째 공간을 바로 찾을 수 없다(임의 접근 Random Access 불가)

 

 

배열에 대한 예제 1)

Program.cs

using System;

namespace CSharpAlgorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            Board board = new Board();
            board.Initialize();

            Console.CursorVisible = false;
            const int WAIT_TICK = 1000 / 30;
            const char CIRCLE = '\u25cf';
            int lastTick = 0;
            while (true)
            {
                
                #region 프레임 관리
                //만약에 경과한 시간이 1/30초보다 작다면
                int currentTick = System.Environment.TickCount;
                if (currentTick - lastTick < WAIT_TICK)
                    continue;
                lastTick = currentTick;
                #endregion

                //입력
                //로직
                //렌더링
                Console.SetCursorPosition(0, 0);

                for (int i = 0; i < 25; i++)
                {
                    for (int j = 0; j < 25; j++)
                    {
                        Console.ForegroundColor = ConsoleColor.Blue;
                        Console.Write(CIRCLE);
                    }
                    Console.WriteLine();
                }
            }
        }
    }
}

 

Board.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace CSharpAlgorithm
{
    class Board
    {
        public int[] _data = new int[25];
        public List<int> _data2 = new List<int>();
        public LinkedList<int> _data3 = new LinkedList<int>();

        public void Initialize()
        {
            _data2.Add(101);
            _data2.Add(102);
            _data2.Add(103);
            _data2.Add(104);
            _data2.Add(105);

            int temp = _data2[2];//103

            _data2.RemoveAt(2);
        }
    }
}

첫 번째는 값을 입력해서 그 값을 찾아서 지워주는 버전이다.

세 번째는 인덱스를 넣어주는 것이다.

 

15번째 라인에 브레이크 포인트를 걸고 F5

F10을 누르면서 하나씩 이동

 

 

마지막 RemoveAt에서 temp 변수가 삭제되는 것을 볼 수 있다.

 

 

배열에 대한 예제 2)

Board.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace CSharpAlgorithm
{
    class MyList<T>
    {
        const int DEFAULT_SIZE = 1;
        T[] _data = new T[DEFAULT_SIZE]; //예약된 총 방의 모음
        public int Count; //실제로 사용중인 데이터 개수
        public int Capacity { get { return _data.Length; } } //예약된 데이터 개수

        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++;
        }
        public T this[int index]
        {
            get { return _data[index]; }
            set { _data[index] = value; }
        }
        public void RemoveAt(int index)
        {
            //101 102 103 104 105 
            for (int i = index; i < Count - 1; i++)
                _data[i] = _data[i + 1];
            _data[Count - 1] = default(T);//남아있는 값 제거
            Count--;
        }
    }
    class Board
    {
        public int[] _data = new int[25];
        public MyList<int> _data2 = new MyList<int>();
        public LinkedList<int> _data3 = new LinkedList<int>();

        public void Initialize()
        {
            _data2.Add(101);
            _data2.Add(102);
            _data2.Add(103);
            _data2.Add(104);
            _data2.Add(105);

            int temp = _data2[2];//103

            _data2.RemoveAt(2);
 
        }
    }
}

 

위에와 같이 같은 라인에 브레이크포인트를 걸고 F5를 누른 다음, 

F10을 이용하여 아래로 내려가면서 값을 비교해본다.

Start!

 

 

 

 

temp 변수에 103의 값이 들어가는 것을 볼 수 있으며, Capacity는 2배씩 증가하고 있는 것을 확인할 수 있다.

 

 

그 이후 값이 103이라는 값이 삭제되고 앞으로 당겨지면서 뒤에 값이 0으로 변경

 

시간복잡도 분석

- 앞에 Board.cs를 가지고 분석

 

O(1) 예외 케이스 : 이사 비용은 무시한다.

 

O(1) 상수

 

 

O(N)

for문에서 데이터에 비례한 루프를 돌고 있다. 

- 추가 혹은 삭제하는 경우는 N에 해당하는 시간복잡도를 갖는다.

 

 

연결리스트에 대한 예제)

Board.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace CSharpAlgorithm
{
    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> newMyLinkedListNode = new MyLinkedListNode<T>();
            newMyLinkedListNode.Data = data;

            //만약에 아직 방이 아예 없다면, 새로 추가한 첫번째 방이 곧 Head이다.
            if (Head == null)
                Head = newMyLinkedListNode;
            
            //기존의 마지막 방과 새로 추가되는 방을 연결
            if (Tail != null)
            {
                Tail.Next = newMyLinkedListNode;
                newMyLinkedListNode.Prev = Tail;
            }
            //새로 추가되는 방을 마지막 방으로 인정
            Tail = newMyLinkedListNode;
            Count++;
            return newMyLinkedListNode;
        }
        public void Remove(MyLinkedListNode<T> MyLinkedListNode)
        {
            //삭제하는 방이 첫 번째 방일 경우,
            //기존의 첫번째 방의 다음 방을 첫번째 방으로 인정
            if (Head == MyLinkedListNode)
            {
                Head = Head.Next;
            }
            //기존의 마지막 방의 이전 방을 마지막 방으로 인정
            if(Tail == MyLinkedListNode)
            {
                Tail = Tail.Prev;
            }
            //
            if (MyLinkedListNode.Prev != null)
            {
                MyLinkedListNode.Prev.Next = MyLinkedListNode.Next;
            }
            if(MyLinkedListNode.Next != null)
            {
                MyLinkedListNode.Next.Prev = MyLinkedListNode.Prev;
            }
            Count--;
        }
    }
    class Board
    {
        public int[] _data = new int[25];//배열
        public MyLinkedList<int> _data3 = new MyLinkedList<int>();//연결리스트

        public void Initialize()
        {
            _data3.AddLast(101);
            _data3.AddLast(102);
            MyLinkedListNode<int> node =  _data3.AddLast(103);//임시저장
            _data3.AddLast(104);
            _data3.AddLast(105);

            _data3.Remove(node);

        }
    }
}

 

 

위에와 같이 같은 라인에 브레이크포인트를 걸고 F5를 누른 다음,

F10을 이용하여 아래로 내려가면서 값을 비교해본다.

Start!

값들이 잘 들어가고 마지막에 삭제도 되는 것을 알 수 있다.

 

 

시간복잡도 분석

- 앞에 Board.cs를 가지고 분석

O(1) 상수 시간

 

O(1) 상수 시간

 

인덱스를 사용할 수 없고 중간 값을 찾고 싶으면 하나씩 타고 찾아나가야 한다.