Java ‐ 컬렉션 프레임워크(LinkedList) - dnwls16071/Backend_Study_TIL GitHub Wiki
📚 노드와 연결
- 낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료구조가 있는데, 바로 노드를 만들고 각 노드를 서로 연결하는 방식이다.
public class Node {
Object object; // 가지고 있는 원소
Node next; // 어떤 노드를 가리키는지
public Node(Object object) {
this.object = object;
}
}
- 노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
- 데이터를 추가할 때 동적으로 필요한 만큼의 노드를 만들어서 연결한다. 배열과 다르게 메모리를 낭비하지 않는다.
- 이렇게 각각의 노드를 연결해서 사용하는 자료 구조를 연결 리스트라고 한다.
📚 직접 구현하는 연결 리스트
- 연결 리스트와 빅오
- 특정 위치에 있는 데이터를 반환할 때 -
O(N)
- 연결 리스트에서 노드에는 다음 노드에 대한 참조가 있다. 인덱스가 주어진다하더라도 배열과 달리(O(1)), 연결 리스트의 경우 O(N)의 시간 복잡도를 보인다.
- 특정 위치의 노드를 찾으려면 결국 순차 탐색으로 가야 하기 때문에 결국 O(N)이 된다.
- 마지막에 데이터를 추가할 때 -
O(N)
- 데이터를 추가하는 연산 자체로만 본다면 O(1)이지만, 실제로는 마지막까지 찾아가야 하기 때문에 O(N)의 시간 복잡도를 가진다.
- 특정 위치에 있는 데이터를 바꿀 때 -
O(N)
- 위와 마찬가지로 특정 위치까지 찾아가는데 O(N)의 시간 복잡도를 가진다.
- 인덱스 조회할 때 -
O(N)
- 위와 마찬가지로 특정 위치까지 찾아가는데 O(N)의 시간 복잡도를 가진다.
📚 배열 리스트와 연결 리스트 성능 비교
| 기능 |
배열 리스트 |
연결 리스트 |
| 인덱스 조회 |
O(1) |
O(N) |
| 검색 |
O(N) |
O(N) |
| 앞에 추가(삭제) |
O(N) |
O(1) |
| 뒤에 추가(삭제) |
O(1) |
O(N) |
| 평균 추가(삭제) |
O(N) |
O(N) |