자료구조의 선형구조(스택, 큐, 테크, 리스트)

이번 포스팅에서는 자료구조의 간단한 정의와 함께 자료구조 중에서 선형구조에 대해 알아보려고 합니다. 우리가 프로그램을 작성할 때 이 프로그램이 얼마나 저장공간을 효율적으로 사용하는지, 이 프로그램을 실행하는 데 있어서 오랜 시간이 걸리지 않는지에 관한 문제는 매우 중요합니다. 자료 구조는 데이터 사이의 관계나 데이터 처리 방법, 데이터의 표현 및 관련 연산 등을 의미합니다. 상황에 맞추어 올바르게 선택한 자료구조는 프로그램의 효율성을 높여주게 됩니다. 자료구조를 이용해서 어떠한 자료를 오름차순 혹은 내림차순으로 정렬하거나, 원하는 데이터만 검색할 수 있으며 특정 자료를 빠르게 찾기 위한 인덱싱 등을 할 수 있습니다. 이러한 자료구조는 선형 구조와 비선형 구조로 나뉘는데 지금부터 선형 구조의 종류와 각각의 자료구조에 대해 설명해보도록 하겠습니다.

 

 

선형 구조와 비선형 구조

앞에서 이야기했듯이 자료구조는 선형 구조와 비선형 구조로 분류할 수 있습니다. 선형 구조의 종류에는 스택, 큐, 데크, 리스트가 있으며 리스트는 또다시 선형 리스트와 연결 리스트로 나뉩니다. 비선형 구조에는 트리와 그래프가 있습니다. 

 

 

선형 구조의 종류

1. 스택

스택은 대표적인 선형 구조의 일환입니다. 이미지로 떠올려보자면 네모난 상자를 생각하면 됩니다. 우리는 책을 정리하려고 하는데, 책의 가로, 세로 크기와 같은 네모난 상자가 있다고 해보겠습니다. 그리고 책을 "가나다라" 순서대로 쌓는다고 생각해보겠습니다. "나"로 시작되는 책을 쌓는 도중 만약 "가"로 시작되는 책을 찾았다면 "가"위에 쌓여있는 "나"로 시작되는 책을 다 빼야 합니다. 그리고 책을 꺼낼 때에는 제일 위에 있는 책부터 한 권씩 꺼내야 합니다. 즉 제일 처음에 상자에 넣었던 책은 제일 아래에 깔려있고, 가장 마지막에 넣었던 책은 상자의 제일 위에 있을 것입니다. 이것이 바로 스택의 원리입니다. 스택의 자료 삽입 및 삭제의 경우 한쪽으로만 가능합니다. 그래서 가장 마지막에 삽입된 데이터가 가장 먼저 삭제됩니다. 이러한 방식을 후입 선출이라고 하며 Last In First Out을 줄여 LIFO 방식이라고도 합니다.

 

2. 큐

큐는 스택과 반대로 먼저 들어간 것이 먼저 나옵니다. 선입 선출 방식으로 First In First Out이라고 해서 FIFO 방식이라고도 합니다. 큐의 경우 기차표를 예매하기 위해 줄 서 있는 사람들, 은행 업무를 보기 위해 대기하는 사람들을 생각해보면 이해하기 쉬울 것입니다. 표를 받기 위해서 차례대로 줄을 서면 매표소 앞에 있는 사람. 즉 줄을 먼저 선 사람부터 예매할 수 있습니다. 은행 업무 또한 업무를 보기 위해서 번호표를 뽑고, 번호표를 뽑은 순서대로 업무가 진행됩니다. 큐도 비슷하게 먼저 들어온 데이터가 먼저 삭제되는 구조를 말합니다. 

 

3. 데크

데크는 큐와 스택의 장점만을 가지고 구성된 자료구조입니다. 양 쪽이 다 뚫린 원기둥을 생각하면 됩니다. 원기둥의 한쪽 구멍으로 구슬을 넣는다고 했을 때 넣은 쪽으로 구슬을 빼낼 수도 있고, 반대편 구멍으로 구슬을 빼낼 수도 있습니다. 마찬가지고 반대편 구멍으로 구슬을 넣고, 뺄 수도 있습니다. 데크도 마찬가지로 양 쪽으로 삽입 및 삭제가 가능합니다. 

 

4. 리스트

- 선형 리스트

리스트는 선형 리스트와 연결 리스트로 다시 분류할 수 있습니다. 대표적은 선형 리스트의 구조로는 배열이 있습니다. 배열은 데이터가 메모리의 연속되는 주소에 저장되는 리스트를 말합니다. 그렇기 때문에 원하는 데이터에 접근하기 위한 속도는 매우 빠릅니다. 하지만 데이터 삽입에 있어서는 빈 공간이 있어야 삽입이 가능하며 내가 3번째 인덱스에 데이터를 넣고 싶은데 3, 4, 5, 6에 다른 데이터가 이미 존재할 경우 3, 4, 5, 6번 데이터를 옆으로 한 칸씩 이동시킨 후 데이터 삽입이 가능합니다. 또한 삭제의 경우도 3번째 데이터를 삭제할 경우 삭제된 공간을 채우기 위해 뒤에 있는 데이터들을 앞 쪽으로 한 칸씩 이동시키는 과정이 필요합니다. 

 

- 연결 리스트

연결 리스트는 선형 리스트와 달리 기억장치 내에 데이터를 연속적으로 저장할 필요는 없습니다. 단지 데이터의 순서에 따라서 포인터를 이용해 연결시킨 구조입니다. 여기서의 데이터는 데이터 값과 포인터 부분으로 되어있으며 노드라고 부릅니다. 노드의 포인터 부분에 다음 데이터의 주소가 들어가 링크가 구성되는 것입니다. 연결 리스트 종류에는 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트 등이 있으며 포인터가 가리키는 방향이 한쪽인지 양 쪽인지, 마지막 데이터의 포인터가 첫 번째의 데이터를 가리키는지 등에 따라 개념과 이름이 달라집니다.