💡 연결 리스트(Linked List)
- 데이터를 감싼 노드(Node) 가 서로 연결되어 있는 구조
- 각 노드는 데이터와 다음 노드를 가리키는 주소(Next) 로 이루어져 있음
Linked List의 특징
- 데이터들이 노드로 구성되어 있음
→ 바로 뒷 노드만 알고 있고 건너 건너에는 어떤 데이터가 있는지 모름
- 메모리의 유연함
→ 크기 제한이 없고 늘리고 줄이고가 자유로움
- 데이터 삽입/삭제 용이함
→ 물리적인 이동 없이 주소만 바꿔주면 됨 (O(1))
- 조회 속도가 느림
→ 처음부터(Head) 하나하나 확인하며 가야 함 (O(N))
💡배열과 LinkedList 비교
| 특징 | 배열(Array) | 연결 리스트(Linked List) |
|---|---|---|
| 저장 방식 | 연속된 메모리 공간에 저장 | 떨어진 공간에 저장되나 주소로 연결 |
| 조회 | 빠름 (O(1)) : 인덱스로 즉시 조회 | 느림 (O(N)) : 첫 노드부터 순차 탐색 |
| 추가/삭제 | 느림 (O(N)) : 데이터를 뒤로 밀거나 당겨야 함 | 빠름 (O(1)) : 주소 연결만 바꾸면 됨 |
| 크기 | 고정(한 번 생성하면 변경 불가) | 동적 |
LinkedList 선언 방법
import java.util.LinkedList;
//1. 선언
LinkedList<String> list = new LinkedList<>();
//2. 값 추가
list.add("Java");
list.add("Spring");
list.add(1, "Boot"); // 중간에 삽입 (인덱스 1번)
//3. 값 삭제
list.remove(1); // 인덱스로 삭제
list.remove("Java");
//4. 값 조회
System.out.println(list.get(0));💡단순 연결 리스트(Singly Linked List)
단순 연결 리스트는 위에서 말한 연결 리스트와 동일한 특징을 가지고 있다
💡이중 연결 리스트(Doubly Linked List)
- 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 갖는 구조
이중 연결 리스트의 특징
-
양방향 탐색
→ 앞(Next)으로도 갈 수 있고 뒤(Prev)로도 이동이 가능하여 단순 연결 리스트보다 탐색이 유연 -
효율적인 검색과 삭제
→ 양쪽 방향에서 삽입과 삭제가 가능 -
메모리 사용이 많다
→ 이전 노드의 주소를 추가로 저장해야 하기 때문에 단순 연결 리스트와 달리 메모리를 더 차지 함
💡원형 연결 리스트(Circular Linked List)
- 마지막 노드의 포인터가 NULL이 아닌 첫 번째 노드를 가리키는 형태를 갖는 구조
→ 마지막 노드의 다음 노드는 첫 번째 노드
→ 첫 번째 노드의 이전 노드는 마지막 노드
