[CS] 자료 구조 (1) : 리스트, 스택, 큐, 트리

자료구조란?

데이터를 표현하고 저장하는 방법이다. 즉, 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.

 

 

배열 (Array) & 리스트 (List)

Array & List

인덱스와 그에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다.

정적으로 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하며, 이 때 각 원소의 주소는 연속적으로 할당된다. C나 Java 등의 언어에서는 Array, Python에서는 List에 해당한다. Python의 리스트는 동적 배열이라고도 하는데 그 이유는 리스트의 크기를 자동으로 조절하기 때문이다. 또한, 배열과 같이 값(Value)을 저장하는 게 아닌 각각의 값이 저장되어 있는 객체를 가리키고 있는 주소값을 가진다.

배열 (Array)

시간 복잡도 : 인덱스를 통해 O(1)으로 접근한다.

장점 : 인덱스로 값을 찾기 때문에 빠른 시간 내에 접근이 가능하다.

단점 : 읽고 쓰는 것만 지원하는 제한된 자료구조이다.

리스트 (List)

시간 복잡도 : 인덱스를 통해 O(1)으로 접근한다. 리스트에 할당된 메모리 공간에 여유가 있을 때 삽입과 마지막 원소의 삭제는 O(1), 메모리가 모자란 경우의 삽입 및 삭제는 O(N)이 걸린다.

장점 : 배열과 동일하게 인덱스로 값을 찾기 때문에 빠른 시간 내에 접근이 가능하며, 파이썬의 리스트는 유연하고 강력한 연산들을 다양하게 지원한다.

단점 : 삽입과 삭제가 느리며, 리스트의 사이즈를 초과한다면 새로운 리스트를 재할당한 후 복사해야한다.

(Java에서는 동적으로 크기가 조절되는 ArrayList가 있음)

 

연결 리스트 (Linked List)

Linked List

노드들의 연결로 이루어진 자료 구조이다.

배열과 달리 사이즈를 미리 정해주지 않아도 된다. 또한, 인덱스 대신 순서가 중요하다. 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성되며 포인터를 사용해서 연결된다.

 

시간 복잡도 : 다음 노드에 대한 참조를 통해 접근하기 때문에 O(N)이며, 삽입과 삭제는 O(1)이 걸린다.

장점 : 동적으로 크기를 할당이 가능하며, 삽입/삭제가 용이하다.

단점 : 임의로 액세스를 허용할 수 없는 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야한다. (이진 검색 수행 불가능) 또한, 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요하다.

 

스택 (Stack)

LIFO 방식으로 나중에 들어온게 먼저 나간다.

원소의 삽입 및 삭제가 한쪽 끝에서만 이루어진다. (top)

함수 호출 시 지역변수, 매개변수 정보를 저장하기 위한 공간 등을 스택으로 사용한다.

 

큐 (Queue)

FIFO 방식으로 먼저 들어온게 먼저 나간다.

원소의 삽입 및 삭제가 양쪽 끝에서 일어난다. (front, rear)

FIFO 운영체제, 은행 대기열, BFS 등에서 사용한다.

단점 : 앞에 요소를 한개 제거하고(dequeue) 첫번째인 front 위치를 한칸 뒤로 이동을 하게 되면, front가 +1 씩 커지면 앞에 있는 빈공간은 필요가 없어진다. 

 

원형 큐

위의 일반 큐의 단점을 보완한 큐이다. 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주한다.

원형 큐는 초기 공백 상태일 때 front와 rear가 0이며, 공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둔다.

단점 : 메모리 공간은 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기가 제한된다.

 

연결리스트 큐

원형 큐를 보완한 연결리스트 큐는 크기가 제한이 없고 삽입, 삭제가 편리하다.

삽입은 tail, 제거는 head로 하면서 삽입/삭제를 스택처럼 O(1)에 가능하도록 구현이 가능하다.

 

우선순위 큐 (Priority Queue)

FIFO 방식이 아닌 데이터를 근거로 한 우선순위를 판단하고, 우선순위가 높은 것부터 나간다.

 

트리 (Tree)

사이클이 없는 무방향 그래프이며, 값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)으로 이루어져있다. 모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부른다.

 

트리의 특징

 

1. 트리에는 사이클이 존재할 수 없다. (만약 사이클이 있다면 그래프)
2. 모든 노드는 자료형으로 표현이 가능하다.
3. 루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.
4. 노드의 개수가 N개면, 간선은 N-1개를 가진다.

 

트리 순회 방법

 

1. 전위 순회 (pre-order) 
2. 중위 순회 (in-order)
3. 후위 순회 (post-order)
4. 레벨 순회 (level-order)

 

1. 전위 순회 (pre-order) : 각 루트(Root)를 순차적으로 먼저 방문하는 방식이다. (Root → 왼쪽 자식 → 오른쪽 자식)

    ex) 1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14

2. 중위 순회 (in-order) : 왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식이다. (왼쪽 자식 → Root → 오른쪽 자식)

    ex) 8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7

3. 후위 순회 (post-order) : 왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문하는 방식이다. (왼쪽 자식 → 오른쪽 자식 → Root)

    ex) 8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1

4. 레벨 순회(level-order) : 루트(Root)부터 계층 별로 방문하는 방식이다.

    ex) 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14