<배열>
배열의 기본 연산에는 삽입, 삭제, 탐색이 있다.
● 연산들의 시간 복잡도
- 삽입
1. 앞이나 가운데에 값을 넣을 때
→ 새로운 값이 들어갈 자리를 확보하기 위해 다른 값들이 한 칸씩 이동해야 함
∴ 시간복잡도는 O(N)이 됨
2. 배열의 맨 뒤에 값을 넣을 때
→ 다른 값들의 이동이 전혀 존재하지 않음
∴ 시간복잡도는 O(1)이 됨
- 삭제
1. 맨 뒤의 값을 지울 때
→ O(1)
2. 맨 뒤가 아닌 다른 값을 지울 때
→ 다른 값들의 이동이 생김
∴ 시간복잡도는 O(N)
- 탐색
1. 원하는 값 찾기
→ 처음부터 모든 값을 훑어야 한다.
∴ 시간복잡도는 O(N)
2. k번째 원소를찾기
→ k-1번째 index를 참조하면 됨
∴ 시간복잡도는 O(1)
● 동적 배열
| 정적 배열 | -배열의 선언과 동시에 그 크기를 정해야 함. - 한 번 선언된 이후에는 크기를 바꿀 수 없음. |
| 동적 배열 | - 메모리 낭비를 해결할 수 있음. - 자유롭게 길이가 줄어들고 늘어날 수 있음. - 정확히 사용하고 싶은 만큼만 공간을 차지하여 사용하는 방식 |
동적 배열의 연산 과정은 정적 배열과 동일하다. 따라서 시간복잡도는 완전히 일치한다.
그러나 메모리를 필요한 만큼만 사용한다는 차이가 있다.
자바에서는 동적 배열을 ArrayList를 이용하여 표현 가능하다.
● ArrayList
- import java.util.ArrayList 호출 필요
- ArrayList<T> name = new ArrayList<>(); 선언 필요. 이 때 T는 타입이고, 참조형만 가능하다.
ex) ArrayList<Integer> v = new ArrayList<>();
- 자주 사용되는 함수
1. add(E) : 맨 뒤에 데이터 E를 추가
2. remove(index) : index 위치에 있는 원소 삭제. (맨 뒤에 있는 원소 삭제는 remove(name.size()-1). ∵ index는 0부터 시작)
3. size() : 현재 ArrayList에 들어있는 데이터 수 반환
4. get(index) : index 위치에 있는 원소 조회
<연결 리스트>
O(1)과 O(N)의 효율 차이는 매우 크다. 때문에 삽입, 삭제가 빈번하다면 배열은 비효율적이다.
이런 문제를 해결하기 위한 자료구조가 연결 리스트이다.
연결 리스트는 탐색은 느리지만(O(N)), 삽입과 삭제는 매우 빠르다(O(1)).
●노드
- 노드란 정보를 담는 하나의 창구이다.
- 일반적으로 연결 리스트에서 하나의 노드는 데이터와 다른 노드로 이동하는 경로를 갖고 있다.
- 연결 리스트는 이러한 노드 여러 개가 모여서 형성되는 구조이다.
●단일 연결 리스트
- 연결 방향이 단방향인 연결 리스트(일방통행구조) →뒤로 돌아갈 수 없음
- 노드는 data와 next 값을 가진다. 단일 연결 리스트에서 next는 바로 옆 노드를 의미한다.
- 예를 들어, node1의 data에 3이 있고 다음 노드가 없다면 next에는 null이 들어있다.
- 만약 next 값에 별다른 값을 넣어주지 않으면 기본으로 null이 된다.
- node2를 만들어 data에 5를 넣어주면 node1.next = node2로 설정하여 두 노드를 연결지을 수 있다.
- 이 때 node1의 netx에는 node2의 data 값이 아니라 node2 자체가 들어간다.
- 노드의 연결을 끊고 싶다면 next에 null을 넣어주면 된다.
- 리스트의 모든 값을 탐색해야 할 때 시작점을 알 수 없다면 모든 값을 탐색했는지 알 수 없으므로 반드시 리스트의 첫 번째 값으 위치를 명시 해야 한다. 그리고 그 값을 head라고 한다.
- 종료 지점(tail)도 알고 있으면 좋다.
- 삽입
1. tail 뒤쪽에 값을 삽입 / head 앞쪽에 값을 삽입
→ next가 가리키는 노드를 변경, tail이 가리키는 노드 변경 (head 앞에 추가하는 것도 비슷하게 하면 됨)
2. head 바로 뒤에 노드 추가
→ 1. 새로운 노드 만들기
2. 새로운 노드의 next 값을 head의 next 값으로 설정
3. head의 next 값을 새로운 노드로 변경
- 삭제
- 연결을 제거
- 삭제하는 노드이 바로 전 노드에서 그 다음 노드로 연결 관계를 변경하는 점만 유의
- head의 삭제 : head의 값을 head.next로 설정
- 탐색
- 삽입, 삭제를 할 때 head와 tail까지 옮긴 이유는 탐색을 원활하게 하기 위해서이다.
● 이중 연결 리스트
- 단일 연결 리스트에 prev가 추가된 것
- 양방향으로 이동 가능
- 삽입, 삭제 시간 복잡도는 O(1), 탐색은 O(N)
- 삽입, 삭제, 탐색
단일 연결 리스트와 흐름은 같으므로 연결 관계에만 포커스를 맞추면 된다.
- List
- 자바에서 이중 연결 리스트 사용을 위해 이용할 수 있다.
- import java.util.LinkedList 헤더 필요
- LinkedList<T> name = new LinkedList<>(); 선언 필요. 이 때 T는 타입, 참조형만 가능.
1. addList(E) : 맨 앞에 데이터 E 추가
2. addLast(E) : 맨 뒤에 데이터 E 추가
3. pollFirst() : 맨 앞에 있는 데이터를 반환하고 삭제
4. pollLast() : 맨 뒤에 있는 데이터를 반환하고 삭제
5. size() : 현재 list에 들어있는 데이터 수 반환
6. isEmpty() : 현재 list가 비어있다면 true, 아니라면 false 반환
7. peekFirst) : 맨 앞에 있는데이터 반환
8. peekLast() : 맨 뒤에 있는 데이터 반환
<Iterator(반복자)>
- 연결 리스트와 별도로 자유자재로 값을 순회할 수 있는 것.
- 배열에서 index를 이용해 특정 위치의 원소를 바로 구할 수 있었던 것처럼 연결 리스트에서는 iterator를 통해 특정 위치를 지정해줄 수 있다.
- iterator 값이 주어지면 prev, next를 통해 삽입, 삭제를 빠르게 할 수 있다.
<앞에서 2번째 데이터 앞에 새 노드 추가 후 3번째 데이터 앞에 새 노드를 추가하는 상황에서>
1. 기존 iterator를 유지하지 않고 삽입 진행
- 2번째 데이터 위치를 찾기 위해 O(N)만큼 소요, 삽입에 O(1)만큼 소요
- 3번째 데이터 위치를 찾기 위해 O(N)만큼 소요, 삽입에 O(1)만큼 소요
2. 기존 iterator를 유지하여 삽입 진행
- 처음에 2번째 데이터 위치를 찾기 위해 O(N)만큼 소요. 이 때 iterator는 head에서 시작하여 계속 next 값을 조회하며 이동. 삽입은 O(1)만큼 소요
- 이미 2번째 위치를 iterator가 가리키고 있으므로 그 다음 위치로 이동하면 3번째 데이터를 찾을 수 있다. 따라서 탐색과 삽입에 각각 O(1)만큼 소요
● ListIterator
- 자바에서 iterator를 사용하기 위해 이용해야 함.
- list 이름이 l일 때 ListIterator<Character> it = l.listIterator(); 형태, iterator는 첫 위치에 놓임
- 맨 끝에서 시작하고 싶다면 ListIterator<Character> it = l.listIterator(l.size()); 형태로 가능
- iterator를 이용하여 list를 순회하는 방법
1. 처음 위치에서 시작 : .hasNext()로 다음 위치로 이동 가능 여부 확인 후 .next()를 통해 이동
2. 맨 뒤에서 시작 : .hasPrevious()로 전 위치로 이동 가능 여부 확인 후 .previous()를 통해 이동
- 자주 사용되는 함수
1. .next(), .previous()
- .hasNext(), .hasPrevious()를 확인하여 true일 때만 진행
- 움직잉는 역할을 하며 동시에 값을 반환해준다
2. it.remove() : 직전에 it.next()했던 원소 제거. 즉 remove() 함수 실행 전에는 반드시 next()가 먼저 실행되어야 함.
3. it.add(E) : 현재 iterator it에 해당하는 위치에 새로운 원소 E 추가
<원형 연결 리스트>
- 한 방향으로 움직이면 다시 출발지로 되돌아온다.
- 기존 연결 리스트에서 tail과 head를 연결하기만 하면 된다.
- 원형이므로 head.prev가 tail이 되므로 보통은 head만 이용한다.
출처: https://inthe-sea.tistory.com/4 [In The Sea:티스토리]
'CNU > 2025 하계 모각코' 카테고리의 다른 글
| [2025 하계 모각코] 3회차 (0) | 2025.07.20 |
|---|---|
| [2025 하계 모각코] 2회차 (0) | 2025.07.13 |
| [2025 하계 모각코] 개인목표 (0) | 2025.06.30 |
