연결리스트 이론
List : 데이터를 순서대로 저장하는 선형 자료구조
-
데이터가 일렬로 쭉 나란히 저장됨.
반대는 비선형(트리, 그래프 등: 가지치기, 분기)
-
가장 대표적으로는
ArrayList와LinkedList가 있다.LinkedList에는 노드가 존재.
| ArrayList | LinkedList |
|---|---|
| 1. 배열과 동일하게 연속된 메모리 공간에 저장됨 | 값과 포인터를 활용한 노드를 연결한 구조 |
| 2. 장점 - 인덱스를 활용하여 빠름 - 메모리 상 데이터만 저장할 수 있음 | 2. 장점 - 중간에 값을 삽입/삭제하는데 효율적 - 동적으로 크기를 조정 |
| 3. 단점 - 중간에 값을 삽입/삭제하는 데에 비용이 큼 - 크기가 제한되어 필요 시 다시 할당해야 함. | 3. 단점 - 특정 값을 찾기에 처음부터 확인함 - 노드는 값과 포인터를 모두 저장해야 해서, 메모리 소비가 큼 |
- LinkedList (위쪽 그림)
각 데이터(2, 23, a, dd, 7a)가 "노드"로 분리되어 있고,
각 노드는 앞/뒤 노드와 "화살표"로 연결됨
head는 시작, tail은 끝
가장 앞/뒤는 null(끝)로 연결
데이터가 메모리상에 "연속적"이지 않아도 됨
노드 추가/삭제 시, 연결만 바꿔주면 됨(빠름)
데이터 하나씩 "따라가며" 접근해야 함(직접 인덱스 접근 느림)
- Array & ArrayList (아래쪽 그림)
모든 데이터가 한 줄로 "연속된 칸"에 저장
각 칸에 0, 1, 2, 3, 4... 인덱스 번호가 붙어있음
한 번에 원하는 위치(인덱스)로 바로 접근 가능(빠름)
중간에 데이터 삽입/삭제 시, "뒤의 모든 값"을 밀거나 당겨야 함(느림)
실제 메모리상에 연속적으로 저장됨
예제
이해를 돕기 위한 예제.
// ArrayList
ArrayList<String> arr = new ArrayList<>();
arr.add("A");
arr.add("B");
arr.add(1, "X");
// 인덱스로 바로 찾아가기에,
// arr.get(10)을 할 경우 바로 10번째 값으로 가게 됨. O(1)의 속도.
// 다만 중간에 삽입/삭제하는 것은 그 뒤의 요소들을 한 칸씩 이동하게 되어 O(n)
System.out.println(arr); // [A, X, B]
// LinkedList
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add(1, "X");
// 여기에서 LinkedList는 포인터가 순차적으로 노드 하나씩을 따라가게 되며 O(n)의 시간을 소요하게 된다.
// 다만 중간 삽입/삭제는 포인터만 바꾸면 되니 O(1)
System.out.println(list); // [A, X, B]리스트가 작을 때에는 그닥 유의미한 차이가 있을 것 같지 않다. 다만 데이터가 수십만, 수백만이 된다면 좀 체감이 될듯...
아직은 몸소 이해할 수 있는 부분이 아닌 것 같다.
연결 리스트 종류
- 단일 연결 리스트 (Singly) : 한 방향으로만 연결됨.
- 이중 연결 리스트 (Doubly) : 앞뒤로 연결되어 -> 양방향 탐색 가능
- 원형 연결 리스트 (Circular) : 마지막 노드가 첫 번째 노드를 가리킴.
// 단일 연결 리스트 (Singly)
class Node {
int value;
Node next; // 다음 노드만 가리킴
}
Node a = new Node(); a.value = 1;
Node b = new Node(); b.value = 2;
a.next = b; // a -> b
// 이중 연결 리스트 (Doubly)
class DNode {
int value;
DNode prev; // 이전 노드
DNode next; // 다음 노드
}
DNode x = new DNode(); x.value = 1;
DNode y = new DNode(); y.value = 2;
x.next = y; y.prev = x; // x <-> y
// 원형 연결 리스트 (Circular)
Node n1 = new Node(); n1.value = 1;
Node n2 = new Node(); n2.value = 2;
n1.next = n2;
n2.next = n1; // n2의 next가 n1을 가리켜 "원"이 됨이건 좀 신기한 것 같다.
(필확) 문제풀이
사용자가 입력한 명령어에 따라 리스트에 값을 추가/삭제합니다.
명령어는 I(마지막에 입력; 양수만 가능), D(마지막 값 삭제), E(종료)로 진행되며,
결과는 종료 이후에 가장 마지막 값, 모든 값, 사이즈를 출력합니다. 비어있다면 -1을 출력합니다.
단, D는 I의 횟수보다 더 많이 입력될 수 없습니다.
-