※ 2021년 12월 29일에 작성된 글입니다.
📋 List
순서를 가진 요소들의 모임
Array vs List
Array | List | |
---|---|---|
물리적 순서와 논리적 순서 | 일치 | 일치하지 않아도 됨 |
크기 | 고정 | 가변 |
메모리 할당 | 정적 | 동적 |
List의 연산
- add
새로운 요소를 리스트의 끝, 처음, 중간에 추가한다. - remove
기존의 요소를 리스트의 임의의 위치에서 삭제한다. - clear
- 모든* 요소를 삭제한다.
- replace
기존의 요소를 대치한다. - contains
리스트가 특정한 요소를 가지고 있는지 확인한다. - get
리스트의 특정 위치의 요소를 반환한다. - size
리스트 안의 요소의 개수를 센다. - isEmpty
리스트가 비었는지 확인한다.
ArrayList
= Dynamic Array
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
A | B | C | D | E |
1차원 배열에 요소들을 순서대로 저장
- 구현이 간단
- 삽입, 삭제 시 오버헤드
ArrayList의 연산
- add
삽입 위치 다음에 요소가 있을 경우 다음 요소들을 이동(shift)해줘야 한다. O(n) - remove
삭제 위치 다음에 요소가 있을 경우 다음 요소들을 이동(shift)해줘야 한다. O(n) - get
배열의 인덱스를 이용해 해당 요소에 접근할 수 있다. O(1)
LinkedList
A → B → C → D → E
노드(node)에 요소와 다음 노드의 주소를 저장
- 구현이 복잡
- 삽입, 삭제가 효율적
LinkedList의 연산
- add
새로운 노드를 생성하고 이전 노드가 새로운 노드를 가리키도록 한다. O(1) ~ O(n) - remove
이전 노드가 삭제하려는 노드의 다음 노드를 가리키도록 한다. O(1) ~ O(n) - get
처음부터 순차적으로 접근한다. O(n)
'CS > 자료구조' 카테고리의 다른 글
[자료구조] Heap (0) | 2024.09.04 |
---|---|
[자료구조] Priority Queue (0) | 2024.09.04 |
[자료구조] Tree (0) | 2024.09.04 |
[자료구조] Queue (0) | 2024.09.04 |
[자료구조] Stack (0) | 2024.09.04 |