[CS Study] 자료구조 (1) - 선형 자료구조

시작하기 전에

첫 번째 챕터는 선형 자료구조입니다.

선형 자료구조(linear data structure)는 연속적으로 데이터가 나열되는 자료구조로 배열, 리스트, 스택, 큐 등이 있습니다.

공부하는 데 많은 도움을 받은 '기술면접대비 CS전공 핵심요약집' 저자분께 감사드립니다.

---

배열이란?

배열(Array)은 정해진 크기만큼 데이터가 일렬로 저장되는 정적(static) 자료구조다.

각 데이터를 배열의 요소(element)라고 하며 데이터를 가리키는 번호를 인덱스(index)라고 한다.

• 접근: O(1), 배열의 첫 번째 데이터에 대한 주소 값에 (데이터 타입의 메모리 크기) * (접근하려는 데이터의 인덱스)를 더하면 된다.
• 검색: O(n), 배열에서 특정 데이터를 검색하면 인덱스 0부터 하나씩 탐색해야 찾을 수 있다.
• 삽입: O(n), 중간 인덱스에 데이터를 추가하는 경우 그 뒤 인덱스부터는 기존 데이터를 뒤로 한 칸씩 미뤄야 한다. 단, 데이터를 추가하려는 위치가 배열의 맨 마지막인 경우에는 O(1)의 시간 복잡도를 갖는다.
• 삭제: O(n), 마찬가지로 중간 인덱스 데이터를 삭제하면 그 뒤 인덱스부터는 기존 데이터를 앞으로 한 칸씩 당겨야 한다. 단, 삭제하려는 데이터가 마지막 데이터라면 O(1)의 시간 복잡도를 갖는다.

---

연결 리스트란?

연결 리스트(Linked List)는 배열과 달리 크기가 정해져 있지 않은 동적(dynamic) 자료구조다.

여러 개의 노드(node)로 구성되어 있으며, 노드는 데이터와 다음 노드가 저장된 주소 값을 가지고 있다.

• 연결 리스트는 헤드(head) 포인터와 테일(tail) 포인터로 시작과 끝을 알 수 있다. 마지막 노드의 다음 노드를 가리키는 주소 값은 NULL이다.
• 연결 리스트는 데이터의 추가 및 삭제가 자유롭다. 기존 노드들의 위치를 변경하지 않고 연결 관계만 변경하면 되기 때문이다.
  대신 배열과 달리 인덱스가 없어서 특정 위치의 데이터에 접근하는 데 배열보다 시간이 오래 걸린다.
• 검색: O(n), 특정 데이터를 검색하려면 첫 번째 노드부터 하나씩 값을 확인해야 한다.
• 추가: O(n), 데이터를 추가하는 연산 자체는 O(1)이나, 데이터를 추가하려는 위치로 이동하기까지 O(n)이 소요된다.
• 삭제: O(n), 마찬가지로 삭제하는 연산 자체는 O(1)이지만, 해당 위치까지 이동하는 데 O(n)이 소요된다.

---

스택이란?

스택(Stack)은 데이터를 쌓는 형태로, 마지막에 들어온 데이터가 먼저 나가는 LIFO(Last In First Out, 후입선출) 형태의 자료구조다.

• 스택에 데이터를 삽입하는 연산을 push라 하고, 스택의 가장 위에 데이터를 저장한다.
• 스택에 있는 데이터를 삭제하는 연산을 pop이라고 하며, 마지막에 저장한 데이터를 삭제한다.
• 스택은 top이라는 변수를 이용해 데이터를 마지막으로 저장한 인덱스를 기억한다.

연산	설명	시간 복잡도
push	스택에 새로운 데이터 삽입	O(1)
pop	스택에서 가장 위에 있는 데이터 삭제	O(1)
peek	스택에서 가장 위에 있는 데이터 확인	O(1)
isEmpty	스택이 비어 있는지 확인	O(1)
isFull	스택이 가득 찼는지 확인	O(1)

 

스택을 사용하는 예로, 웹 브라우저에서 뒤로가기 할 때 등 최근에 처리한 작업들을 하나씩 꺼낼 때 사용한다.

---

큐란?

큐(Queue)는 데이터가 순차적으로 들어오는 형태로, 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out, 선입선출) 형태의 자료구조다.

• 큐의 맨 앞을 front, 맨 뒤를 rear라고 한다.
• 큐에 데이터를 추가하면 큐의 맨 뒤에 데이터가 삽입되는데, 이를 인큐(enqueue)라고 한다.
• 큐에서 데이터를 삭제하면 큐의 맨 앞에서 삭제되며, 이를 디큐(dequeue)라고 한다.

연산	설명	시간 복잡도
enqueue	큐의 rear에 새로운 데이터 삽입	O(1)
dequeue	큐의 front에서 데이터 삭제	O(1)
peek	큐의 front에 있는 데이터 확인	O(1)
isEmpty	큐가 비어 있는지 확인	O(1)
isFull	큐가 가득 찼는지 확인	O(1)

 

큐를 사용하는 예로, 운영체제에서 프로세스가 CPU를 할당받기 전까지 준비하는 준비 큐가 있다.

그 외에도 어떠한 작업을 처리할 때 작업 요청이 들어온 순서대로 처리하기 위해 주로 큐를 사용한다.

---

마치며

선형 자료구조를 살펴봤습니다. 다음 글에서는 비선형 자료구조를 알아보겠습니다.