자료구조란?
☞ 컴퓨터에서 처리할 자료를 효율적으로 관리하고 구조화시키기 위한 학문입니다. 즉, 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업을 의미합니다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 합니다. 자료구조에는 여러 종류가 있으며, 각각의 자료구조는 각자의 연산 및 목적에 맞춰져 있습니다. 오늘은 가장 기본적인 자료구조인 스택, 큐, 연결리스트에 대해서 알아보겠습니다.
25.1 ) 스택 ( STACK )
☞ 스택은 한 쪽에서만 자료를 넣고 뺄 수 있는 LIFO( Last In First Out ) 형태의 자료 구조입니다. 쉽게 생각해 어떤 통 안에 물건을 하나씩 넣는데 꺼낼 때는 물건이 쌓여 있기 때문에 ①번 물건을 꺼내고 싶어도 가장 위쪽의 물건부터 하나씩 차례대로 빼야 원하는 물건을 뺄 수 있습니다.
☞ 스택에서는 PUSH 연산을 통해 새로운 자료를 넣을 수 있고, POP 연산을 통해 마지막으로 넣은 자료를 뺄 수 있습니다.
☞ 스택 구조에서 자료를 삽입하고 지우고 검색하는 시간 복잡도(BIG-O)를 살펴보면 다음과 같습니다.
- Insertion : O(1) ( PUSH를 하여 값을 넣기만 하면 되기 때문에)
- Deletion : O(1) ( POP을 하여 값을 빼기만 하면 되기 때문에)
- Search : O(n) (n은 스택의 사이즈를 의미하며 상황에 따라 달라집니다.)
25.2) 큐 ( QUEUE )
☞ 큐(Queue)는 먼저 넣은 자료를 먼저 뺄 수 있는 FIFO( First In First Out ) 형태의 자료구조입니다. 쉽게 생각해 매표소에 줄을 선다고 생각하면 됩니다. 가장 먼저 줄을 선 사람이 가장 먼저 매표를 할 수 있고, 늦게 와서 줄을 선 사람은 앞에 줄을 선 사람들이 모두 매표가 끝나고 자신의 차례가 와야 매표를 할 수 있습니다.
☞ 큐(Queue)에서는 ENQUEUE 연산을 통해 새로운 자료를 넣을 수 있고, DEQUEUE 연산을 통해 가장 먼저 넣은 자료를 뺄 수 있습니다.
☞ 큐(Queue) 구조에서 자료를 삽입하고 지우고 검색하는 시간 복잡도(BIG-O)를 살펴보면 다음과 같습니다.
- Insertion : O(1) ( ENQUEUE를 하여 값을 넣기만 하면 되기 때문에)
- Deletion : O(1) ( DEQUEUE를 하여 값을 빼기만 하면 되기 때문에)
- Search : O(n) (n은 큐의 사이즈를 의미하며 상황에 따라 달라집니다.)
25.3) 연결리스트( LINKED LIST )
☞ 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다. 이름에서 알 수 있듯이 데이터를 담고 있는 노드들이 연결되어 있는데 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 됩니다. 그리고 가장 처음에 만들어진 노드가 HEAD 노드이고, 가장 마지막에 위치하며 다음 노드가 NULL인 노드가 TAIL 노드입니다.
☞ 연결리스트의 예를 들자면 한 회사에 있는 직원들의 신상명세 자료를 만드는데 각 직원들의 신상명세서를 노드라고 생각하고 1번 직원의 신상명세서 안에 2번 직원의 신상명세서가 어디에 있는지 표시를 해 놓는 것입니다. 쉽게 생각해 비엔나 소세지를 줄줄이 엮어 놓았다고 생각하면 됩니다.
☞ 연결리스트에서는 어떤 값을 가진 노드를 만든 후, 이전 노드의 포인터가 자신을 가리키게 하고 자신의 포인터가 다음 노드를 가리키게 수정하면 서로 연결이 되고 삽입이 완료됩니다. 반대로 특정 노드를 삭제할 경우, 특정 노드의 포인터를 NULL로 만들고 이전 노드가 특정 노드의 다음 노드를 가리키도록 포인터를 수정하면 연결리스트에서 특정노드의 삭제가 완료됩니다.
☞ 연결리스트 구조에서 자료를 삽입하고 지우고 검색하는 시간 복잡도(BIG-O)를 살펴보면 다음과 같습니다.
- Insertion : O(1) ( 특정 위치에 노드를 넣기만 하면 되기 때문에)
- Deletion : O(1) ( 특정 위치에 있는 노드를 제거하기만 하면 되기 때문에)
- Search : O(n) (n은 연결리스트의 길이를 의미하며, 마지막 노드를 찾으려면 연결리스트의 끝까지 모든 노드를 검색해서 찾아봐야 하기 때문에)
