💡 연결 리스트
원소를 저장할 때, 다음 원소가 있는 위치를 포함하여 저장하는 자료구조
-
k번째 원소를 확인/변경 :
O(K)소요 → 첫번째 주소값을 통해 차례대로 두번째, 세번째, .., K번째 원소에 도달 -
임의의 위치에 원소를 추가 & 제거 :
O(1)소요 (추가하고 싶은 위치의 주소값을 아는 경우, 모르면 첫번째부터 탐색해야 하므로 K+1) → 뒤의 요소를 모두 옮기는 것이 아닌, 다음 원소의 주소값만 변경하면 됨 -
원소들이 메모리에 연속적으로 위치하지 않아 메모리 할당이 쉬움 → 캐시 적중률은 낮음
-
각 원소가 다른 원소의 주소값을 가지고 있어야 하기 때문에, N에 비례하는 추가 공간이 필요하다.
📒 종류
📝 단일 연결 리스트
각 원소가 자신의 다음 원소의 주소를 가지고 있는 연결 리스트
📝 이중 연결 리스트
각 원소가 자신의 이전 원소와 다음 원소의 주소를 가지고 있는 연결 리스트
📝 원형 연결 리스트
끝이 처음과 연결되어 있는 연결 리스트 (단일 & 이중 모두 가능)
📒 배열 vs 연결 리스트
배열과 연결 리스트는 선형 자료구조이다!
| ✅ | 배열 | 연결 리스트 |
|---|---|---|
| N번째 원소의 접근 | O(1) | O(N) |
| 임의의 위치에 원소 추가 & 제거 | O(N) | O(1) |
| 메모리 상의 배치 | 연속 | 분할 |
| 추가적으로 필요한 공간 | - | O(N) |
📒 구현
배열에 원소를 저장하고, 각 원소의 이전 원소와 다음 원소의 주소값을 각각의 배열에 저장 → 0번에서 시작한다고 가정, 이전 혹은 다음 원소가 없으면 -1
dat[]: 원소의 값pre[]: 이전 원소의 주소값nxt[]: 다음 원소의 주소값
traverse(): 원소값 출력 → 배열의 순서대로 출력하는 것이 아닌, 연결 리스트 순서대로 출력
void traverse() {
int cur = nxt[0]; // 현재 주소값
while(cur != -1) { // nxt[] = -1 : 다음 원소가 없다는 뜻
System.out.println(dat[cur] + ' ');
cur = nxt[cur];
}
}insert(): 임의의 위치에 원소 추가
void insert(int addr, int num) {
dat[unused] = num; // 1. 새로운 원소 생성
pre[unused] = addr; // 2. 새 원소의 pre : 삽입 위치의 주소값
nxt[unused] = nxt[addr]; // 3. 새 원소의 nxt : 삽입 위치의 nxt
// 4. 삽입 위치 다음 원소의 pre : 새 원소의 주소값 (삽입 위치에서 다음 원소가 있는 경우)
if(nxt[addr] != -1) pre[nxt[addr]] = unused;
nxt[addr] = unused; // 4. 삽입 위치의 nxt : 새 원소의 주소값
unused++; // 5. 다음에 값을 추가할 주소
}erase(): 임의의 위치의 원소 삭제
void erase(int addr) {
nxt[pre[addr]] = nxt[addr]; // 1. 이전 위치의 nxt : 삭제할 위치의 nxt
if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr]; // 2. 다음 위치의 pre : 삭제할 위치의 pre
}📒 연습문제
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
LinkedList<Character> list = new LinkedList<>();
String s = br.readLine();
for(int i=0;i<s.length();i++) {
list.add(s.charAt(i));
}
int n = Integer.parseInt(br.readLine());
int cursor = list.size();
for(int i=0;i<n;i++) {
String order = br.readLine();
switch (order.charAt(0)) {
case 'L' : if(cursor > 0) cursor--; break;
case 'D' : if(cursor < list.size()) cursor++; break;
case 'B' : if(cursor > 0) { list.remove(cursor - 1); cursor--; } break;
case 'P' : list.add(cursor, order.charAt(2)); cursor++;
}
}
StringBuilder sb = new StringBuilder();
for(char ch : list) {
bw.write(ch);
}
bw.close();
}
}
: 위 코드를 제출하니 시간 초과가 떴다.. 아무래도 삽입/삭제 시 해당 인덱스를 바로 찾아가는 것이 아닌 첫 시작점부터 차례대로 찾아가야 하므로 O(N)의 시간 복잡도를 가지게 되어 발생한 문제인 것 같다. 그렇다면 이를 어떻게 O(1)로 풀 수 있을까?
✔️ ListIterator
Iterator를 상속한 인터페이스 : 양방향 탐색 가능
✅ ListIterator를 사용해서 해당 인덱스를 처음부터 순서대로 찾아가는 것이 아닌, 실제 커서가 특정 위치에서 한 칸씩 움직이는 형태로 동작하므로, O(1)의 시간 복잡도를 가지게 된다!
-
list.listIterator(): 가장 앞에서부터 탐색 시작 → 문제의 조건은 제일 끝에서 시작하므로list.size()를 시작 위치로 지정 -
hasPrevious(): 이전 원소가 있는지 확인 (역방향) →previous(): 이전 원소 리턴 -
hasNext(): 다음 원소가 있는지 확인 (정방향) →next(): 다음 원소 리턴 -
remove():next()또는previous()가 가리키는 원소 제거 -
add(): 현재 탐색 위치에 원소 추가
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
LinkedList<Character> list = new LinkedList<>();
String s = br.readLine();
for(int i=0;i<s.length();i++) {
list.add(s.charAt(i));
}
int n = Integer.parseInt(br.readLine());
ListIterator<Character> cursor = list.listIterator(list.size());
for(int i=0;i<n;i++) {
String order = br.readLine();
switch (order.charAt(0)) {
case 'L' : if(cursor.hasPrevious()) cursor.previous(); break;
case 'D' : if(cursor.hasNext()) cursor.next(); break;
case 'B' : if(cursor.hasPrevious()) { cursor.previous(); cursor.remove(); } break;
case 'P' : cursor.add(order.charAt(2));
}
}
StringBuilder sb = new StringBuilder();
for(char ch : list) {
bw.write(ch);
}
bw.close();
}
}
🙇🏻♀️ 참고 : 백준 1406번) 에디터(ListIterator)
➕ 스택을 사용한 풀이도 있었는데 그건 스택 강의 듣고 다시 보기..
🙇🏻♀️ 출처 : [바킹독의 실전 알고리즘] 0x04강 - 연결 리스트
