자료구조 : 선형구조와 비선형구조

데이터를 저장하고 관리하는 방식에 따라 자료구조는 크게 선형구조와 비선형구조로 나눌 수 있습니다. 각각의 자료구조는 고유한 특성과 장단점을 가지며, 적절한 활용이 필요합니다. 이 글에서는 선형구조와 비선형구조의 대표적인 자료구조들의 특성과 장단점을 자세히 알아보겠습니다.

 

선형구조

선형구조는 데이터가 연속적으로 나열되는 구조를 말합니다.

배열 (Array)

특성: 연속적인 메모리 위치에 저장됩니다. 인덱스를 사용하여 원하는 위치의 데이터에 쉽게 접근할 수 있습니다.
장점: 빠른 데이터 접근이 가능합니다.
단점: 크기가 고정되어 있어 확장이 어렵습니다. 중간에 데이터를 삭제하거나 삽입할 때 비효율적입니다.

int[] numbers = new int[5] {1, 2, 3, 4, 5};
Console.WriteLine(numbers[2]);  // 3을 출력합니다.

 

연결 리스트 (Linked List)

특성: 각 요소는 데이터와 다음 요소에 대한 참조(또는 링크)로 구성됩니다.
장점: 동적으로 크기를 확장할 수 있습니다. 데이터 삽입과 삭제가 용이합니다.
단점: 인덱스 접근이 느리며, 추가적인 메모리를 사용합니다.

LinkedList<string> fruits = new LinkedList<string>();
fruits.AddLast("Apple");
fruits.AddLast("Banana");
fruits.AddLast("Cherry");
Console.WriteLine(fruits.First.Value);  // Apple을 출력합니다.

스택 (Stack)

특성: LIFO(Last In First Out) 방식으로 데이터를 저장하며, 가장 마지막에 들어간 데이터가 가장 먼저 나오는 구조입니다.
장점: 데이터의 삽입과 삭제가 빠르며, 구현이 간단합니다.
단점: 스택의 최상단 위치에서만 작업이 가능합니다.

Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
Console.WriteLine(stack.Pop());  // 3을 출력합니다.

큐 (Queue)

특성: FIFO(First In First Out) 방식으로 데이터를 저장하며, 가장 먼저 들어간 데이터가 가장 먼저 나오는 구조입니다.
장점: 데이터의 순서를 보장하며, 다양한 활용이 가능합니다(예: 작업 스케줄링).
단점: 큐의 앞부분에서 삭제와 뒷부분에서 삽입이 이루어지기 때문에, 중간 데이터에 접근하려면 추가적인 작업이 필요합니다.

Queue<string> queue = new Queue<string>();
queue.Enqueue("First");
queue.Enqueue("Second");
queue.Enqueue("Third");
Console.WriteLine(queue.Dequeue());  // First를 출력합니다.

 

비선형구조

 

비선형구조는 데이터가 계층적이거나 그래프 형태로 저장되는 구조를 말합니다.

트리 (Tree)

특성: 계층적인 구조를 가집니다. 하나의 부모 노드 아래에 여러 자식 노드가 연결되어 있습니다.
장점: 계층적인 데이터를 효율적으로 표현할 수 있습니다. 탐색 및 삽입, 삭제가 빠르게 수행될 수 있습니다.
단점: 설계가 복잡하며, 구현이 어려울 수 있습니다.

class TreeNode<T> {
    public T Value { get; set; }
    public List<TreeNode<T>> Children { get; set; }

    public TreeNode(T value) {
        Value = value;
        Children = new List<TreeNode<T>>();
    }
}

TreeNode<string> rootNode = new TreeNode<string>("Root");
TreeNode<string> childNode1 = new TreeNode<string>("Child1");
TreeNode<string> childNode2 = new TreeNode<string>("Child2");

rootNode.Children.Add(childNode1);
rootNode.Children.Add(childNode2);

그래프 (Graph)

특성: 노드(Node)와 그 사이의 관계를 나타내는 간선(Edge)로 구성됩니다.
장점: 복잡한 관계의 데이터를 표현할 수 있습니다. 네트워크 구조의 표현이 가능합니다.
단점: 구현이 복잡하며, 탐색 알고리즘이 복잡할 수 있습니다.

class GraphNode<T> {
    public T Value { get; set; }
    public List<GraphNode<T>> Neighbors { get; set; }

    public GraphNode(T value) {
        Value = value;
        Neighbors = new List<GraphNode<T>>();
    }
}

GraphNode<string> nodeA = new GraphNode<string>("A");
GraphNode<string> nodeB = new GraphNode<string>("B");

nodeA.Neighbors.Add(nodeB);  // A에서 B로의 간선 추가
nodeB.Neighbors.Add(nodeA);  // B에서 A로의 간선 추가 (양방향)

 

결론

선형구조와 비선형구조의 자료구조는 각각 고유한 특성과 장단점을 가지고 있습니다. 문제의 특성과 요구 사항에 따라 적절한 자료구조를 선택하고 활용하는 것이 중요합니다. 초보자도 이를 통해 데이터 관리의 기본 원칙을 이해하고, 실제 프로그래밍에 적용할 수 있을 것입니다.