리스트
리스트 자료구조는 데이터를 일렬로 저장하는 자료구조입니다. 그렇기에 중복된 데이터의 저장을 막지않는다.
리스트는 제목과 마찬가지로 ArrayList , LinkedList 2가지로 구분됨
ArrayList
ArrayList는 배열을 기반으로한 리스트 입니다.
ArrayList는 사용할수있는 capacity가 설정되어있고 최대 capacity만큼 데이터를 넣을수있는 자료구조입니다. 여러가지 언어마다 제공해주는 라이브러리마다 size가 capacity보다 커질경우 최적의 알고리즘으로 capacity 증가시켜 배열을 새로 할당한후 이전의 배열값에 새로운 배열에 데이터를 복사하여 list를 이용함
배열로 이루어진 형태이기때문에 인덱스 접근이 수월하며 저장 공간이 일렬로 이루어짐
사진은 정렬된것처럼 보이겠지만 정렬을 이루는 자료구조는 아님
여기서 2번 인덱스에 10이란 데이터를 주가하고싶다면
2번인덱스에 10번을 삽입후 3,4,5 데이터는 뒤쪽으로 이동 하게됨
그렇다면 여기서 1번 인덱스를 삭제한다면?
와 같은 형태가 됩니다.
이것을 c++로구현한 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
#define MAX_CAPACITY 100
class List {
private:
int arr[MAX_CAPACITY];
int size = 0;
public:
void insert(int idx,int data) {
if (size >= MAX_CAPACITY) {
cout << "Memory overFlow" << endl;
exit(-1);
}
//일렬로 맞추기위해
if (idx > size)
idx = size;
for (int i = size - 1; i >= idx; i--)
arr[i + 1] = arr[i];
arr[idx] = data;
size++;
}
void push(int data) {
insert(size, data);
}
void pop_back() {
remove(size - 1);
}
void remove(int idx) {
if (size <= 0) {
cout << "list Empty" << endl;
exit(-1);
}
if (idx < 0 || idx >= size) {
cout << "index error" << endl;
exit(-1);
}
for (int i = idx; i < size-1; i++)
arr[i] = arr[i + 1];
size--;
}
int find(int data) {
for (int i = 0; i < size; i++)
if (arr[i] == data)
return i;
return -1;
}
void print() {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int getSize() {
return size;
}
int get(int idx){
if (idx < 0 || idx >= size) {
cout << "index error" << endl;
exit(-1);
}
return arr[idx];
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
List list;
for (int i = 1; i <= 5; i++) {
list.push(i);
}
list.insert(2, 10);
list.remove(1);
list.print();
}
|
cs |
여기서 잘보실것은 마지막으로
데이터를 맨뒤에 삽입했을때와 ,맨뒤의 데이터를 제거했을때입니다.
데이터를 임의이 위치에 삽입했을 때 삽입한 데이터의 뒤에있는 데이터들이 뒤로 밀려 해당하는 데이터개수만큼 밀어줘야합니다.
그러나 마지막 인덱스에 삽입했을경우는 미는 과정이 필요없기대문에 O(1) 시간복잡도를 가집니다.
또한 임의의 위치를 삭제했을경우 그제된 데이터는 필요없기때문에 뒤에있는 데이터들을 앞으로 당겨줘야합니다.
그러나 마지막 인덱스를 삭제했을경우 당겨오는 과정이 필요없기때문에 이과정만 O(1) 의 시간복잡도를 가집니다.
LinkedList
LinkedList는 노드를 연결로 기반한 리스트 입니다.
ArrayList와 사용하는 방법은 동일하나 어떻게 사용하냐의 따라 시간등의 차이가 있습니다.
LinkedList의 size는 가변적입니다.
node가 추가될때마다 사이즈가 증가하는 구조입니다.
메모리 할당
- Array 에서, Memory 는 Array 가 선언되자 마자 Compile time 에 할당되어집니다.
- 이것을 Static Memory Allocation 이라고 부릅니다.
- Stack section 에 memory 할당이 이루어집니다.
- LinkedList 에서, Memory 는 새로운 node 가 추가될 때 runtime 에 할당되어집니다.
- 이것을 Dynamic Memory Allocation 이라고 부릅니다.
- Heap section 에 memory 할당이 이루어집니다.
요소 접근
- Array 는 Random Access 를 지원합니다.
- element 들을 index 를 통해 직접적으로 접근할 수 있습니다.
- ex) arr[0], arr[1]
- 따라서, 특정 element 에 접근하는 시간 복잡도는 O(1) 입니다.
- element 들을 index 를 통해 직접적으로 접근할 수 있습니다.
- LinkedList 는 Sequential Access 를 지원합니다.
- 어떤 element 에 접근할 때, 처음 부터 순차적으로 접근하면서 찾아야 합니다.
- 따라서, 특정 element 에 접근할 때의 시간 복잡도는 O(N) 입니다.
삽입 및 삭제
- Array
- 인덱스로 접근 후 삽입 및 삭제 O(1) + 전체 배열 요소를 1씩 Shift O(N)
- LinkedList
- 삽입하려는 위치 접근 후 삽입 및 삭제 O(N)
- 만약, 맨 앞과 뒤에 삽입 및 삭제한다면 O(1)
| ArrayList | LinkedList | |
| get(첫번째) | O(1) | O(1) |
| get(마지막) | O(1) | O(1) |
| get(임의) | O(1) | O(n) |
| insert(첫번재) | O(n) | O(1) |
| insert(마지막) | O(1) | O(1) |
| insert(임의) | O(n) | O(n) |
| remove(첫번째) | O(n) | O(1) |
| remove(마지막) | O(1) | O(1) |
| remove(임의) | O(n) | O(1) |
결론
- 데이터 접근이 주 업무일 경우 → Array
- 데이터 수정이 주 업무일 경우 → Linked List
- 전반적인 내용을 보면, Array 보다 Linked List 의 사용이 훨씬 좋아보이지만,
- 일반적인 알고리즘 문제를 풀 때는 Linked List 보다 Array 가 훨씬 빠르고 편리합니다.
- 대부분의 알고리즘 문제는 메모리 공간의 범위를 파악할 수 있도록, N 의 크기가 주어지기 때문입니다.
- 따라서, 배열의 크기를 MAX 로 초반에 잡는다면, Array 가 훨씬 더 편리하고 빠릅니다.
- Linked List는 요소를 삽입, 삭제할 때마다 메모리의 할당,해제가 일어납니다.
- 이런 작업은 시간복잡도에 포함되지는 않지만, 시스템 콜(System Call)을 사용하는 구문은 시간 소요가 꽤 걸립니다.
사진 출처 : https://girawhale.tistory.com/8
출처 : https://wooono.tistory.com/281
'Computer Science > 자료구조' 카테고리의 다른 글
| 자료구조 hash (0) | 2022.04.22 |
|---|---|
| [CS 면접] 자료구조 정렬의 종류, 정렬의 차이 (0) | 2022.03.24 |
| [CS 자료구조] 그래프와 트리의 차이 (0) | 2022.03.07 |
| [자료구조] CS 공부 스택 vs 큐 (스택으로 큐구현 , 큐로 스택구현) (0) | 2022.02.24 |
| [자료구조] Queue 구현하기 (0) | 2020.08.08 |
