uk's study

1. 선형 리스트(ArrayList)

 배열과 같이 연속되는 기억장소에 저장되는 리스트

선형 리스트의 특징

1. 가장 간단한 자료구조이다.

2. 접근속도가 빠르다.

3. 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.

4. 기억장소를 연속적으로 배정하기 때문에 기억장소 사용 효율은 밀도가 1로서 가장 좋다.

5. 자료의 개수가 n개일 때 삽입 시의 평균 이동 횟수는 (n+1)/2이고, 삭제 시에는 (n-1)/2이다.

6. 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거롭다.

2. 연결 리스트(LinkedList)

연결 리스트는 자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키지만, 자료 순서에 따라 노드의 포인터 부분을 이용하여 연결시킨 자료 구조

연결 리스트의 특징

1. 노드의 삽입, 삭제 작업이 용이하다.

2. 기억공간이 연속적으로 놓여 있지 않아도 저장이 가능하다.

3. 연결을 위한 포인터가 필요하기 때문에 선형 리스트에 비해 기억공간 이용 효율이 좋지 않다.

4. 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.

5. 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

6. 희소 행렬 을 링크드 리스트로 표현하면 기억장소가 절약된다.

7. 노드 구조를 사용하는 트리 등을 표현할 때 가장 적합한 자료 구조이다.

Abstract

데이터를 표현하는 한 방법인 트리는 정점과 선분으로 형성된 그래프의 특수한 형태이며, 임의의 두 정점 사이에 사이클을 형성하지 않는 비선형 데이터 구조이며, 주로 포인터를 사용하여 표현한다.

1. 트리

트리 구조는 정보의 항목들이 가지(Branch)로 연관되어 데이터를 구성하고 있다. 트리는 어떤 데이터를 저장하는 노드들이 루트 노드라 불리는 노드를 가장 상위로 하여 계층적으로 구성되어 있는 데이터 구조로써, 한 노드에는 그의 자식(child) 노드들이 연결되며, 자식 노드들은 또 자신의 자식을 가지는 계층 구조이며, 사이클을 허용하지 않는다. 임의 노드의 바로 상위 노드를 그 노드의 부모(Parent) 노드라고 한다.

트리는 계층적인 데이터를 표현하는 데 사용되며 여러 분야에서 매우 널리 사용되는 중요한 데이터 구조이다.

1.1 트리의 정의

트리의 정의는 다음과 같은 조건을 만족하면서 하나 이상의 노드로 구성된 유한된 집합체이다.

1. 단 하나의 루트 노드가 존재해야 한다.
2. 루트 노드에서 각 노드로 가지로 연결되어야 한다.
3. 순환(Loop)를 허용하지 않는다.
4. 루프 노드를 제외한 나머지 노드들은 n(n>=0)개의 서로 분리된 부분집합으로 나누어 진다. 임의의 각 부분집합도 트리 구조이며 이것을 서브 트리라고 한다.

1.2 트리 용어

트리에서 사용되는 용어를 설명하기 위해 다음 그림을 예로 들어본다.

노드(Node)는 트리를 구성하는 정점(Vertex)이며, A,B,C,D,E 등을 말한다. 가지(Edge)는 노드 간의 관계를 표시하는 연결선이며, 레벨(Level)은 루트 노드의 레벨을 1로 하고, 그 다음 자식 노드는 2, 그 다음 자식 노드의 자식 노드는 3.. 으로 표시 하는 것이다.

루트 노드(Root Node)는 레벨이 가장 낮은 노드인 A가 그림에서의 루트 노드가 되며, 차수(degree)는 서브 트리의 개수로써 A의 차수는 3, B의 차수는 2, C의 차수는 1, K,L,F,G,M,I,J의 차수는 0이 된다.

깊이(depth)는 임의의 트리에서 노드가 가지는 최대 레벨이며, 앞의 그림에서는 4가 깊이가 된다. 자식(child) 노드는 어떤 노드에 연결된 다음 레벨의 노드이다. 예를 들어 A의 자식 노드는 B,C,D이며 B의 자식 노드는 E,F 이다.

부모(Parent) 노드는 어떤 노드에 연결된 상위 노드이다. 예를 들어 B의 부모 노드는 A이다. 형제(Sibling) 노드는 같은 부모 노드를 가진 노드를 말한다. 예를 들어 B,C,D 노드는 형제 노드이다.

단말 노드(Terminal Node 또는 Leaf)는 차수가 0인 노드이며, 앞의 그림에서는 K,L,F,G,M,I,J 가 해당한다. 중간 노드는 차수가 0이 아닌 노드이며, 단말 노드를 제외한 노드를 말한다.

숲(Forest)는 분리된 트리의 집합으로써 앞의 그림을 가지고 다음과 같이 표현할 수 있다.

1. 스택(Stack)

데이터 구조의 하나로써 원소의 삽입과 삭제가 한쪽 끝에서만 일어나는 선형 리스트이다. 원소들의 삽입, 삭제가 일어나는 부분을 top라고 하며, 원소를 스택에 넣는 것을 push, 스택에서 원소를 꺼내는 것을 pop이라고 한다. 스택에서는 나중에 들어간 원소가 먼저 꺼내어지므로 후입선출(LIFO, Last-In, First Out)이라고 한다.

스택은 주로 어떤 내용을 기억시켰다가 다시 이용하고자 할 때 사용되며 컴퓨터 알고리즘에 자주 쓰이는 데이터 구조이다. 스택의 활용 예로써, 운영체제에서 인터럽트가 발생한 경우에 복귀 주소의 저장이나 산술 계산에 사용된다.

2. 큐(Queue)

데이터 구조의 하나로써 큐도 여러 데이터 항목을 일정한 순서로 입출력하기 위한 선형 데이터구조로써, 선형 리스트의 한쪽 끝에서는 삽입 동작만, 반대쪽에서는 삭제 동작만 이루어진다.

큐에는 한 방향으로 데이터 항목들이 삽입/삭제되는 선형 큐와 시작점과 끝점이 서로 연결되어 있는 환형 큐가 있다. 먼저 입력되는 데이터를 먼저 삭제하므로 선입선출(FIFO, First in First out)이라고 한다.

큐는 rear, front 노드를 이용하여 삽입, 삭제를 구현한다.

큐의 활용 예로써 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 사용한다

• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (은행 카운터)
• 프린터의 출력 처리

3. 데크(Deque : Double-ended queue)

데크는 스택과 큐를 혼합한 상태이며 비슷한 동작으로 양쪽 끝 모두에서 삽입과 삭제가 일어나도록 설계 된 데이터 구조이다. 스택의 한쪽 끝에서 삽입과 삭제가 동시에 일어날 경우 그 위치(주소)를 알려주는 포인터가 1개 필요하였듯이 데크에서는 2개의 포인터가 필요하다. 데크는 선형구조이므로 배열을 이용할 수 있다.

데이터 구조는 선형 구조와 비선형 구조로 분류할 수 있다.

선형 구조로는 배열과 행렬이 있으며 스택, 큐, 데크는 일반적으로 선형 리스트로 사용한다. 비선형 구조로는 트리,그래프 등이 있다.