[C#] 선형 자료구조 (Array, Dynamic Array, Linked List)

<그냥 하는 말... >

취준을 위해 다시 정리해본다. 대학교 1학년 때 잘 이해도 안되는 연결리스트를 c로 직접 구현하느라 애를 많이 썼던 기억이 아직도 생생하다... 

 

선형 구조는 자료를 순차적으로 나열한 형태이다.

• 배열, 동적 배열
• 연결 리스트
• 스택 / 큐

 

배열 (Array)

배열은 고정된 크기의 연속적인 메모리 블록에 데이터를 저장한다. 모든 요소가 동일한 데이터 타입을 가지며, 인덱스를 사용하여 요소에 접근할 수 있다.

 

장점

1. 빠른 인덱스 접근: 특정 인덱스의 요소에 O(1) 시간 복잡도로 접근할 수 있다.
2. 메모리 효율성: 요소들이 연속적으로 저장되므로 메모리 오버헤드가 적다.

단점

1. 고정 크기: 배열의 크기를 초기화할 때 정해야 하며, 이후에는 크기를 변경할 수 없다.
2. 비효율적인 삽입 및 삭제: 요소를 삽입하거나 삭제할 때, 특히 배열의 중간에서 수행할 경우, 많은 요소를 이동시켜야 하므로 계산 비용이 크다.

// 배열 선언
int[] _data = new int[10];

_data[0] = 0;
_data[1] = 1;
_data[2] = 2;

int temp = _data[2];

 

 

동적 배열 (Dynamic Array)

동적 배열은 크기를 동적으로 조정할 수 있는 배열이다. 일반적으로 크기가 다 차면 더 큰 새로운 배열을 할당하고 기존 배열의 요소들을 복사한다.

 

장점

1. 가변 크기: 필요에 따라 크기를 동적으로 조정할 수 있다.
2. 빠른 인덱스 접근: 배열과 마찬가지로 특정 인덱스의 요소에 O(1) 시간 복잡도로 접근할 수 있다.

단점

1. 재할당 비용: 크기를 늘릴 때 새로운 배열을 할당하고 기존 요소들을 복사해야 하므로 O(n) 시간이 소요된다.
2. 메모리 낭비 가능성: 현재 필요하지 않은 공간을 위해 메모리가 사용될 수 있다.

< C# 에서의 동적 배열 >

// C# 에서는 List<T> 클래스를 통해 Dynamic Array 자료구조를 제공한다.
public List<int> _data2 = new List<int>();

_data2.Add(1);            // 데이터 추가
_data2.Add(2);
_data2.Add(3);
_data2.Add(4);
_data2.Add(5);

int temp = _data2[2];      // 데이터 접근

_data2.Remove(2);          // 값에 의한 삭제
_data2.RemoveAt(0);        // 인덱스에 의한 삭제
_data2.Clear();            // 모든 요소 삭제

// 이 외에도 추가적인 기능이 많음

 

dynamic array를 직접 구현해 보면, 아래와 같이 구현할 수 있다.

 class MyDynamicArray<T>
 {
 	// 생성시 처음으로 할당되는 배열 크기
     const int DEFAULT_SIZE = 1;
     // 배열을 얼마나 늘릴지를 결정하는 배율
     const int MULTIPLIER = 2;

     T[] ary = new T[DEFAULT_SIZE];

	 // 배열 원소의 개수
     public int Count;
     // 배열에 할당된 크기
     public int Capacity { get { return ary.Length; } }

     public void Add(T item)
     {
     	 // 배열이 가득 찬 경우, 배열 크기 증가
         if (Count >= Capacity)
         {
             T[] newAry = new T[Capacity * MULTIPLIER];
             
             // 기존 원소들을 새 배열로 복사
             for (int i = 0; i < Count; i++)
                 newAry[i] = ary[i];

             ary = newAry;
         }

         // 새로운 원소 추가
         ary[Count] = item;
         Count++;
     }

	 // 인덱스로 접근
     public T this[int index]
     {
         get { return ary[index]; }
         set { ary[index] = value; }
     }

	 // 인덱스 위치의 값 삭제 후 뒤의 원소 이동
     public void RemoveAt(int index)
     {
         for (int i = index; i < Count - 1; i++)
             ary[index] = ary[index + 1];

		// 마지막 원소를 dafault 값으로 변환 int 자료형의 경우 0으로 초기화 된다.
         ary[Count - 1] = default(T);
         Count--;
     }
 }

 

 

연결 리스트 (Linked List)

연결 리스트는 각 요소가 데이터와 하나 이상의 포인터(다음 요소를 가리키는)를 가지는 노드들로 구성된 데이터 구조이다.

ex.) 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List)

 

장점

1. 동적 크기: 요소를 필요에 따라 동적으로 추가하거나 제거할 수 있다.
2. 효율적인 삽입 및 삭제: 특정 위치에서의 삽입 및 삭제가 O(1) 시간 복잡도로 가능하다. 단, 삽입 및 삭제 위치를 찾는 데 O(n) 시간이 걸릴 수 있다.

단점

1. 느린 접근 시간: 특정 요소에 접근하려면 처음부터 차례로 접근해야 하므로 O(n) 시간이 소요된다.
2. 메모리 오버헤드: 각 노드가 데이터 외에 포인터를 저장해야 하므로 메모리 사용량이 증가한다.

< C# 에서의 연결리스트 >

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

// LinkedList 뒤에 원소 추가
_data3.AddLast(0);
_data3.AddLast(1);

// 추가한 노드를 반환
LinkedListNode<int> node = _data3.AddLast(2);

_data3.AddLast(3);
_data3.AddLast(4);

// 해당 노드를 삭제
_data3.Remove(node);

 

Linked List를 직접 구현해 보면 아래와 같다.

// 노드 클래스
class MyNode<T>
{
    public T Data;         // 노드에 저장되는 데이터
    public MyNode<T> Next; // 다음 노드를 가리키는 포인터
    public MyNode<T> Prev; // 이전 노드를 가리키는 포인터
}

class MyLinkedList<T>
{
    public MyNode<T> Head = null; // 리스트의 첫 번째 노드
    public MyNode<T> Tail = null; // 리스트의 마지막 노드
    public int Count = 0;         // 리스트의 노드 개수

    // 리스트의 끝에 새로운 노드를 추가
    public MyNode<T> AddLast(T data)
    {
    	// 새로운 노드 생성
        MyNode<T> newNode = new MyNode<T>(); 
        newNode.Data = data;               

        // 리스트가 비어 있을 경우, Head를 새로운 노드로 설정
        if(Head == null)
            Head = newNode;

        // Tail의 다음 노드를 새로운 노드로 설정
        if(Tail != null)
        {
            Tail.Next = newNode;
            newNode.Prev = Tail; // 새로운 노드의 이전 노드를 Tail로 설정
        }

        Tail = newNode; // Tail을 새로운 노드로 갱신
        Count++;        // 노드 개수 증가

        return newNode;
    }

    public void Remove(MyNode<T> node)
    {
        // 제거할 노드가 Head인 경우, Head를 다음 노드로 갱신
        if(Head == node)
            Head = Head.Next;

        // 제거할 노드가 Tail인 경우, Tail을 이전 노드로 갱신
        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--;
    }
}

 

 

 

요약

• 배열: 고정 크기, 빠른 인덱스 접근, 비효율적인 삽입/삭제.
• 동적 배열: 가변 크기, 빠른 인덱스 접근, 재할당 비용 발생, 메모리 오버헤드.
• 연결 리스트: 동적 크기, 빠른 삽입/삭제, 느린 접근 시간, 메모리 오버헤드.