계층적인 구조를 가진다.
일반적으로 같은 타입으로만 이루어진다.
불변성(immutability)을 가진다.
위에 언급된 모두 해당
-1
0
1
2
컴파일 타임(compile time)
런타임(runtime)
비정상 종료 시
발생하지 않는다.
10 bytes
14 bytes
40 bytes
44 bytes
0 byte
4 bytes
Binary tree
Process scheduling
Caching
Spatial locality
Node list
Array list
Linked list
Unordered list
O(1), O(1)
O(1), O(n)
O(n), O(1)
O(n), O(n)
Head pointer
Tail pointer
Node pointer
Node
O(1)
O(n)
O(n^2)
O(n^3)
단일 연결 리스트 (singly linked list)
이중 연결 리스트 (doubly linked list)
원형 연결 리스트 (circular linked list)
Array로 구현된 linked list
삽입 정렬 (insertion sort)
기수 정렬 (radix sort)
이진 탐색 (binary search)
Array는 linked list보다 space locality가 좋다.
데이터 삭제는 array보다 linked list가 간단하다.
Linked list에서 random access는 허용되지 않는다.
평균적인 탐색 시간은 array보다 linked list가 짧다.
Insertion sort
Merge sort
Quick sort
Heap sort
첫 번째 노드일 때만
첫 번째 노드가 아닐 때만
마지막 노드일 때만
마지막 노드가 아닐 때만
고정된 크기
할당된 크기보다 적게 사용할 때 메모리 낭비가 발생
인덱스 기반 삭제
인덱스를 통한 요소 접근
O(log n)
리스트의 어느 방향으로든 탐색할 수 있다.
단일 연결 리스트보다 많은 공간이 필요하다.
삽입과 삭제가 단일 연결 리스트보다 시간이 더 걸린다.
단일 연결 리스트보다 구현하기 쉽다.
O(n * log n)
Head가 null을 가리키는 경우는 없다.
탐색 속도가 더 빠르다.
다음 노드를 가리키는 포인터가 null을 가리키는 경우는 없다.
마지막 노드가 무엇인지 알 수 없다.
실행 취소 동작
CPU 스케줄링
재귀 함수 호출
Hash table 구현
Head에 노드를 추가하는 시간 복잡도는 O(1)이다.
모든 노드는 다음 노드를 가리키고 있다.
마지막 노드를 삭제하는 시간 복잡도는 O(n)이다.
이중 연결 리스트보다 공간을 적게 사용한다.
1차원 행렬은 1차원 배열로 표현할 수 있다.
2차원 행렬은 2차원 배열로 표현할 수 있다.
2차원 행렬은 1차원 배열로 표현할 수 없다.
Sparse matrix를 표현하는 데에는 비효율적이다.
Row-minor order
Column-minor order
Row-major order
Column-major order
4
5
1차원 배열
2차원 배열
Stack
© Seunggon Kim