[자료구조 / Data Structure] 자료구조, 리스트
자료구조 (Data Structure)
자료구조는 컴퓨터 상 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조이다.
자료구조의 현명한 선택을 통해 효율적인 알고리즘을 사용할 수 있게 하여 성능을 향상시킨다.
자료구조의 분류 (Classification of Data Structure)
선형 구조 (Linear Structure)
데이터를 연속적으로 연결한 자료구조.
즉, 데이터 요소가 순차적 또는 선형으로 배열되고, 각 요소들이 이전 및 다음 elements와 붙어있는 구조를 선형 구조라고 한다.
종류로는 리스트, 스택, 큐, 데크가 있다.
비선형 구조 (Non - linear Data Structure)
데이터를 비연속적으로 연결한 자료구조.
즉, 데이터가 비순차적 또는 비선형적으로 배열되어 있다. 비선형 구조에서는 단일 실행만으로는 모든 elements를 탐색할 수 없다.
종류로는 트리, 그래프가 있다.
선형 구조
리스트 (List)
| 종류 | 설명 |
| 선형 리스트 (Linear list) | 배열과 같이 연속되는 기억 장소에 저장되는 리스트 선형 리스트의 대표적인 구조로는 배열(Array) 가장 간편한 자료구조이며, 접근 구조가 빠름 자료의 삽입, 삭제 시 기존 자료의 이동이 필요 |
| 연결 리스트 (Linked List) | 노드의 포인터 부분으로 서로 연결시킨 리스트 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트로 구분 노드의 삽입, 삭제가 선형 리스트와 달리 편리 연결을 위한 포인터가 추가되어 저장 공간이 추가로 필요 포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림 |
1. 배열 (Array)
2. 연결 리스트 (Linked List)
연결 리스트란? (What is linked list?)
Linked list is a linear data structure, in which elements are not stored at a contiguous location, rather they are linked using pointers. Linked List forms a series of connected nodes, where each node stores the data and the address of the next node.
2.1 연결 리스트의 장점? (Why linked list data structure needed?)
1. 동적 데이터 구조 (Dynamic Data structure)
- 메모리 크기는 삽입 또는 삭제에 따라 할당되거나, 할당 해제될 수 있다.
- The size of memory can be allocated or de-allocated at run time based on the operation insertion or delection.
2. 삽입과 삭제의 용이 (Ease of Insertion/Deletion)
- 배열보다 간단하다. 요소의 삽입과 삭제 이후 요소를 이동할 필요가 없다. 주소만 업데이트하면 되기 때문이다.
- The insertion and deletion of elements are simpler than arrays since no elements nedd to shifted after insertion and deletion, Just the address needed to be updated.
3. 효율적인 메모리 활용 (Efficient Memoty Utilization)
- 크기가 증가하거나 감소하는 동적 데이터 구조이므로, 메모리 낭비를 방지할 수 있다.
- Linked List is a dynamic data structure the size increases or decreases as per the requirement so this avoids the wastage of memory.
4. 구현 (Implementation)
- 스택, 큐, 해시맵 등과 같은 연결 리스트를 사용해 다양한 데이터 구조를 구현할 수 있다.
- Varius advanced data structures can be implemented using a linked list like a stack, queue, hash maps, etc.
2.2 연결 리스트 종류 (Types of linked lists)
주로 3개의 연결 리스트 유형이 있다.
1. Single-linked list
2. Double-linked list
3. Circular-linked list
단일 연결 리스트 (Single linked list)
- 단일 연결 리스트는 각 노드에서 후속 노드에 대한 참조를 가지고 있다. 따라서, 선행 노드로는 이동할 수 없고 포인터를 이용해 후속 노드로만 이동할 수 있다.
이중 연결 리스트 (Doubly linked list)
- 이중 연결 리스트는 각 노드가 선행 노드와 후속 노드에 대한 링크를 갖는 리스트이다.
단일 연결 리스트와 이중 연결 리스트 비교 (Single linked list vs Doubly linked list)
| SLL | DLL |
| SLL nodes contains 2 filed-data field and next link field. | DLL nodes contains 3 filed-data filed, a previous link field and a next link field. |
| In SLL, the traversal can be done using the next node link only. Thus traversal is possible in one direction only. | In DLL, the traversal can be done using the previous node link or the next node link. Thus traversal is possible in both directions (forward and backward). |
| The SLL occupies less memory than DLL as it has only 2 fields. | The DLL occupies more memory than SLL as it has 3 fields. |
| Complexity of insertion and deletion at a given position is O(n). | Complexity of insertion and deletion at a given position is O(n/2) = O(n) becuase traversal can be made from start or from the end. |
| Complexity of deletion with a given node is O(n), because the previous node nedds to be known, and traversal takes O(n). | Complexity of deletion with a given node is O(1) because the previous node can be accessed easily. |
| We mostly prefer to use singly linked list for the execution of stacks. | We can use a doubly linked list to execute heaps and stacks, binary trees. |
| When we do not need to perform any searching operation and we want to save memory, we perfer a singly linked list. | In case of better implementation, while searching, we prefer to use doubly linked list. |
| A single linked list consumes consumes less memory as compared to the doubly linked list. | The doubly linked list comsumes more memory as compared to the sinly linked list. |
즉, 단일 연결리스트는
- 한 방향으로만 접근이 가능하다. 따라서 DLL 보다 적은 메모리를 차지한다.
- 시간 복잡도는 O(N)이다.
반면, 이중 연결 리스트는
- 양향으로 접근이 가능하다.
- 시간 복잡도는 O(n/2)=O(n)이다.
- 삭제 복잡도는 선행 노드에 쉽게 접근할 수 있으므로 O(1)이다.
- 탐색에 용이하다.
- SLL 보다 더 많은 메모리를 차지한다.
원형 연결 리스트 (Circular linked list)
- 노드가 원형 형태로 연결되어 있다. 첫 번째 노드와 마지막 노드가 연결되어있다. 따라서, 마지막 노드의 링크가 NULL이 아닌 첫 번째 노드의 주소를 가리킨다.
원형 연결리스트는 Circular singly linked list, Circular doubly linked list의 두 가지 형태로 나뉠 수 있다.
- Circular singly linked list
- 마지막 노드는 첫 번째 노드의 포인터를 가리킨다.
- 시작이나 끝이 없다. 노드의 다음 부분에는 NULL 값이 없다.
- Circular doubly linked list
- 이중 원형 연결리스트는 후속 및 선행 노드가 포인터로 연결되어 있다.
- 마지막 노드는 포인터로 첫 번째 노드를 가리키고, 첫 번째 노드는 포인터로 마지막 노드를 가리킨다.
Reference
https://www.geeksforgeeks.org/data-structures/linked-list/singly-linked-list/