자료구조 - 선형구조(2/2) 덱, 선형 리스트, 연결 리스트

덱, 데크(Deque)

Deque는 Double-ended Queue로 말 그대로 Queue가 2개 겹쳐있는 것처럼 생각해도 된다.

 

Queue의 간단한 설명은 아래링크에 있다.

https://beetr.tistory.com/94

자료 구조 - 자료구조 개념과 선형구조 (1/2)

 

• 데이터를 저장하는 기억 장치가 양쪽 모두에 있다.
  • 입, 출력이 양쪽에서 일어난다.
• 데이터의 입출력이 일어나는 위치를 왼쪽에서 가리키면 Left Pointer, 오른쪽은 Right Pointter
• 두 Pointer는 데이터가 입력되거나 출력될 때마다 1씩 증가하거나, 감소한다.

Deque 특징

• 데이터가 메모리에 가득 찼거나, 비었을 경우 스크롤(Scroll) 또는 자체(Shef) 방법을 이용해 조절한다.
• Scroll : 출력은 양쪽에서 모두 가능하지만, 입력은 한쪽에서만 사용
• Shef : 입력은 양쪽에서 모두 가능하지만, 출력은 한쪽에서만 사용

 

 

선형리스트(Linear List)

개념

• 선형리스트는 배열과 같이 연속되는 기억 공간에 저장되는 리스트 구조다.
• 대표적으로는 배열(Array)이고, 대부분 선형 리스트는 배열이라고 볼 수 있다.
• 가장 간단한 구조이고, 접근 속도가 빠르다.
• 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.
• 자료를 삽입, 삭제할 때 자료의 이동이 필요하기 때문에 삽입, 삭제가 많은 작업에는 적절하지 않다. 

배열 구조

배열은 같은 자료형의 요소들이 동일한 크기로 순차적으로 나열되어 있는 집합이다.

인덱스에 의해 구분이 된다.

데이터마다 변수 이름을 따로 두지 않아 처리가 간편하다

int[] arr = new int[100]; // arr이 배열의 이름
arr[0] = 1; // 0 이 index
arr[1] = 2; // 1 이 index

 

배열의 특징

• 고정 크기의 메모리 공간을 사용한다. (위에서 new int[100]처럼 초기화 시 공간을 지정)
• 연속적인 기억 장치를 사용하므로 액세스 시간이 짧고 구조가 간단하다.
• 연속적이기 때문에 중간에 삽입/삭제가 어렵다.
• 논리적인 순서와 물리적인 순서가 같다. (arr[0]은 논리적으로 첫 번째를 의미하고, 물리적으로도 첫 번째이다.

위와 같이 2를 배열의 두 번째로 보낸다고 가정하면, 2번째 이후의 항목들을 뒤로 한 칸씩 미뤄야 하기 때문에 중간의 삽입이 어렵다고 할 수 있고, 삭제도 마찬가지로 맨 처음 수를 삭제한다고 하면 2번째 이후의 항목을 앞으로 한칸씩 당겨야 하기 때문에 중간삭제가 어렵다고 할 수 있다.

 

연결리스트 (Linked List)

개념

• 자료들을 선형 리스트처럼 연속으로 배열시키지 않고, 포인트를 이용해 임의의 공간에 연결해 기억시킨다.
• 데이터의 삽입, 삭제가 용이하다
• 연속적이지 않아도 자료를 저장할 수 있다.
• 다음 자료를 가리키기 위한 포인터 기억 공간이 추가적으로 필요하다.
• 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 선형 리스트보다 느리다.

구조

• 데이터끼리 연결할 포인터를 포함해 기억 장치를 구성한다.
• 두 번째 데이터가 입력되면 첫번째 데이터가 두 번째의 포인터를 기억한다.

특징

• 포인터를 포함한 자료 구조를 노드(Node)라고 하고, 노드에는 연결을 하기 위한 포인터의 추가 공간이 필요하다.
• 포인터는 실제 데이터를 기억하는 공간이 아니기 때문에, 실제 데이터의 수와 저장되는 밀도를 고려해 설계 필요하다.
• 노드들이 포인터로 연결되어 있어 검색이 느리다.
• 중간 노드의 연결이 끊어지면, 다음 노드를 찾기 힘들다.
• 연결 리스트에 비해 배열은 원소를 임의의 위치에 삽입하는 비용이 크다.
• 연결 리스트에 비해 배열은 임의의 위치에 있는 원소를 접근할 때 효율적이다.

 

종류

단일은 이전 노드가 다음 노드를 가리키는 단방향 연결이다.

그림에는 표현이 제대로 안 되어있기 때문에, 화살표가 왼쪽에서 오른쪽으로 있다고 생각하기!

단일

단일은 단일 연결 리스트, 단일 환형 연결 리스트가 있다.

공통적인 특징은 다음과 같다.

• Atom(Node를 구성하는 요소)의 위치를 나타내는 포인터가 1개 뿐이다.
• 노드 삽입은 어디서든 이루어진다.
• 1개의 포인터를 사용하기 때문에 이중 연결 리스트보다는 기억 장소를 적게 차지한다.

 

1. 단일 연결 리스트 (Single Linked List)

• 현재 노드에서 이전 노드로의 접근은 항상 첫 번째 노드부터 다시 시작한다.
• 논리적인 순서와 물리적인 순서가 다를 수도 있다.
• 마지막 노드의 포인터에는 NULL 값이 기억된다.

2. 단일 환형 연결 리스트 (Single Circular Linked List)

• 최종 노드의 포인터는 최초의 노드를 가리키도록 구성되어 있다.
• NULL 포인터가 존재하지 않는 리스트 구조이다.

이중

이중은 이중 연결 리스트와, 이중 환형 연결 리스트가 있다.

공통적인 특징은 다음과 같다.

• 한 노드에는 앞, 뒤 총 2개의 포인터가 있다.
• 2개의 포인터를 사용하기 때문에 기억 장소를 많이 사용한다.
• 노드의 삽입과 제거가 쉽다.
• 앞의 노드를 찾는데 효율적이다.

 

 

이중 연결 리스트 (Double Linked List)

 

이중 환형 연결 리스트 (Double Circular Linked List)