[자료구조] 선형 자료구조 : List, Stack, Queue, DeQue

공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 

 

---

 

선형구조 : List

1. 선형 리스트(Linear List)

연속되는 기억장치에 저장되느 자료구조로, 대표적으로 배열(array)이 있다. 

원하는 정보가 있으면 해당하는 Index에 바로 찾아가면 되므로 접근속도가 빠르다는게 특징이다.

단, 데이터 삽입-삭제시 데이터를 이동해주어야하므로 번거롭다.

 

화요일이 없어져서 수요일이 2가 되도록 데이터가 이동되었다.

 

2. 연결 리스트(Linked List)

자료를 임의의 공간에 기억시키고, 순서에 따라 포인터로 연결시킨 자료구조이다.

기억공간이 연속적이지 않고, 포인터를 통해 사슬처럼 앞<->뒤가 연결되어있는 것이 특징이다. 

따라서 배열과 같은 선형 리스트와 비교했을 때 데이터(원소)의 삽입과 제거가 용이하지만 접근 속도가 느리다는 단점도 존재한다. 

 

또한 연결 리스트는 원하는 형태대로 리스트를 구현할 수 있어 종류도 다양하다.

 

가장 기본이 되는 단순 연결 리스트 (앞-> 뒤 순서)

마지막 노드가 헤드 포인터로 연결되는 단순 원형 연결 리스트 

노드끼리 연결되어 있는 이중 연결 리스트

 

이 외에도 트리형 연결 리스트 등 다양하게 응용되어 사용된다. 

 

스택(Stack)

스택은 리스트의 한 쪽 끝으로만 자료의 삽입-삭제가 이루어지는 자료구조 형태로 주로 임시저장 기능에서 자주 활용된다.

프로그램의 실행 취소, 뒤로가기 기능 등이 여기에 해당된다. 스택은 기본적으로 나중에 입력된 데이터가 먼저 삭제되는

후입선출(LIFO)방식이다. 이 때 삽입을 PUSH, 삭제를 POP이라고 말한다. 

 

Overflow와 Underflow

스택 구조에서 발생하는 메모리 관련 에러로, 모든 메모리가 채워져있는 상태에서 Push가 이루어질 경우 overflow가 발생한다.

예를 들어 함수가 자기 자신을 계속 호출하는 등의 무한 호출 구조로 잘못 만들면 오류가 발생하는데, 이는 overflow에 해당된다. 

 

반대로 메모리가 비워져있는 상태에서 POP을 시도하면 Underflow가 발생한다. 

 

내용

 

큐(Queue)

한 쪽에서는 데이터의 삽입이, 한족에서는 삭제가 이루어지는 자료구조이므로 선입선출(FIFO)이 특징이다.

프린터의 출력 처리 등 순서대로 처리되어야하는 경우 사용된다. 

 

- 프런트 포인터 : 가장 먼저 입력된 데이터 기억공간으로, 삭제 작업을 진행한다.

- 리어 포인터 : 가장 마지막에 입력된 데이터의 기억 공간으로, 삽입 작업을 진행한다.

 

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

 

 

덱(DeQue)

두 개의 포인터를 사용하여 삽입과 삭제가 양쪽 끝에서 모두 발생할 수 있는 자료구조로, Stack과 Queue의 장점만을 활용하여 구성된 자료구조이다. 

문서 편집의 Undo/Redo로 활용되며, 덱에도 입력제한덱, 출력제한덱 등이 존재한다.

 

 

 

입력제한덱(Scroll)

한쪽에서는 삽입을 제한해서 삭제만 진행되도록 만드는 변형된 덱. 삭제는 양방향에서 가능하다.

 

출력제한덱(Shelf)

한쪽에서 삭제를 제한해서 삽입만 진행되도록 만드는 변형된 덱.  삽입은 양방향에서 가능하다. 

 

 

 

참고자료

 

연결 리스트 - 위키백과, 우리 모두의 백과사전

 

[자료구조 with C언어] 연결리스트 (Linked List)