1. 기본 세팅
after[i] = i번 위치의 다음 위치
before[i] = i번 위치의 이전 위치
A[i] = i번 위치의 실제 데이터
#노드 수
n = 8
#데이터
A = [3,1,7,2,5,4,9,10]
#다음 위치, 이전 위치
after = [-1]*8
before = [-1]*8
단일 연결 리스트면, after나 before 하나만 사용해서 한방향으로 연결하고
이중 연결 리스트면 after, before 모두 사용해서 양방향으로 연결
0 > 1 > 2 > 3 > 4 > 5 > 6 > 7로 연결되어있다고 가정하자
반대로 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7로도 연결되어있다고 가정해
for i in range(n-1):
after[i] = i+1
for i in range(1,n):
before[i] = i-1
print(after)
print(before)
[1, 2, 3, 4, 5, 6, 7, -1]
[-1, 0, 1, 2, 3, 4, 5, 6]
-1은 연결된 곳이 없다는 뜻임
7번 노드는 after[7] = -1이므로 그 다음 노드가 없다는 뜻이고
0번 노드는 before[0] = -1이므로 그 이전 노드가 없다는 뜻
2. 탐색 연산
연결 리스트에서 어떤 원소 a가 몇번째 위치에 있는가?
head에서 시작해서 방향을 따라 O(N)으로 탐색하여 a를 찾아야한다.
head를 0번이라고 한다면... i != -1이 아니면 while문을 반복하여, i = after[i]로 after 방향을 따라 탐색해준다
[3,1,7,2,5,4,9,10]
i = 0
a = 4
while i != -1:
if A[i] == a:
break
i = after[i]
print(i)
5
3. 삭제 연산
어떤 원소 a를 연결 리스트에서 삭제하려면?
그 원소 a의 위치를 O(N)에 찾고 그 노드가 i라면, i를 삭제하고, i의 이전 노드와 i의 다음 노드를 서로 연결시켜주면 된다.
다만 a의 위치를 이미 알고 있다면 O(1)에 가능하다.
5번 노드를 삭제하고 싶다면?
5번 노드의 이전 노드 before[5]와 5번 노드의 이후 노드 after[5]를 서로 연결시킨다.
after[before[5]] = after[5]
before[after[5]] = before[5]로 수정하면 된다.
이후에 after[5] = -1, before[5] = -1로 삭제한다면 그림적으로는 이쁘긴한데 반드시 필요한게 아니라면 그럴 필요는 없긴하다
i = 5
before[after[i]] = before[i]
after[before[i]] = after[i]
#before[i] = -1
#after[i] = -1
#A[i] = -1
print(before)
print(after)
다만 주의해야할 점은 시작 노드와 끝 노드를 삭제할 때이다.
시작 노드의 경우는 before이 없고, 끝 노드의 경우는 after이 없기 때문에
생각하지 않으면 에러날 수 있다
i = 5
a = after[i]
b = before[i]
if a != -1:
before[a] = b
if b != -1:
after[b] = a
#before[i] = -1
#after[i] = -1
#A[i] = -1
print(before)
print(after)
시작 노드나 끝 노드 삭제하면 딱히 연결할건 없지
만약에 시작 노드나 끝 노드에 데이터를 넣어두지 않고 시작+1~ 끝-1 사이에서만 데이터를 다룬다면?
그러면 이런 if문으로 예외를 둘 필요가 없겠지?
왜냐하면 데이터가 없는 노드를 삭제할 이유는 없으니까
그러면 삭제하려는 모든 노드는 before과 after값을 가지기 때문에 서로 연결하면 된다
4. 삽입 연산
현재 5번 노드를 삭제한 연결 리스트에서 0 > 1 > 2 > 3 > 4 > 6 > 7에서
2번 노드와 3번 노드 사이에 데이터 6을 넣고 싶다면 어떻게 해야할까?
0 > 1 > 2 > (6) > 3 > 4 > 6 > 7
이렇게 넣으면 될거잖아?
3번 노드 4번 노드 6번 노드 7번 노드는 뒤로 한칸씩 밀어서 4번,5번,7번,8번 노드로 이름을 바꾸고
0 > 1 > 2 > 3 > 4 > 5 > 7 > 8 이렇게 하면 2번 노드와 3번 노드 사이에 6을 넣고 이름을 3번 노드로 한건가..?
이렇게 뒤로 밀 필요 없이, 그냥 비어있는 위치에 새 데이터를 넣기만 하면 된다.
0,1,2,3,4,5,6,7번 인덱스에 [3 1 7 2 5 4 9 10] 각각 있잖아
그러면 8번 인덱스에 6을 넣어서 [3 1 7 2 5 4 9 10 6]하고
0 > 1 > 2 > 8 > 3 > 4 > 6 > 7 이렇게 넣으면 끝
after[2] = 8, before[8] = 2
after[8] = 3, before[3] = 8 이렇게 연결해주면 끝
m = 6
A.append(m)
unused = 8 #사용하지 않는 방 번호
a = 2
b = 3
after[2] = unused
before[unused] = 2
after[unused] = 3
before[3] = unused
unused += 1 #다음 빈방
print(after)
print(before)
배열을 이용해서 구현할때 주의해야할 점은, after, before을 원래 가지고 있는 데이터보다 충분히 크게 잡아야한다는 점
안그러면 위처럼 인덱스 에러날 가능성이 높다
배열은 한번 잡으면 크기를 못바꾸니까
5. 갱신 연산
i번째 위치의 데이터 a를 다른 데이터 b로 바꾸고 싶다면?
그냥 A[i] = b로 하면 되니까 O(1)에 가능
이런건 after, before뿐만 아니라 각 위치 i번 위치의 데이터 값들을 A로 관리하고 있어야한다는거지
6. 원형 연결리스트
원형 연결리스트는, 시작과 끝이 연결되어있는 형태이다.
선형 연결리스트는 0 > 1 > 2 > 3 > 4 > 5 ... > n으로 끝이 있지만,
원형 연결리스트는 n번을 시작인 0번과 연결해주고, 0번은 끝인 n번과 연결해주면 된다.
그냥 시작과 끝을 연결해주기만 하면 끝
따라서 원형 연결리스트는 끝없이 이동이 가능하다.
left = [-1]*(n+1)
right = [-1]*(n+1)
A = list(range(n+1))
#head인 경우 tail과 연결하고, tail인 경우는 head와 연결함
for i in range(1,n+1):
if i-1 == 0:
left[i] = n
else:
left[i] = i-1
if i+1 == n+1:
right[i] = 1
else:
right[i] = i+1
https://www.acmicpc.net/problem/1158
deque로도 해결할 수 있지만, 이중 원형 연결리스트를 구현해서도 해결할 수 있다.
1번부터 n번까지 이중 원형 연결리스트를 구현하고, 1번부터 k번째 탐색해서 그 위치를 삭제하고,
삭제한 위치부터 다음 k번째를 탐색해서 삭제하고,
삭제한 위치부터 다음 k번째를 탐색해서 삭제하고,...
n,k = map(int,input().split())
left = [-1]*(n+1)
right = [-1]*(n+1)
A = list(range(n+1))
for i in range(1,n+1):
if i-1 == 0:
left[i] = n
else:
left[i] = i-1
if i+1 == n+1:
right[i] = 1
else:
right[i] = i+1
answer = []
x = 1
for _ in range(n):
for i in range(k-1):
x = right[x]
answer.append(A[x])
a = left[x]
b = right[x]
right[a] = b
left[b] = a
x = b
print('<',end='')
for i in range(len(answer)-1):
print(answer[i],end=', ')
print(answer[-1],end='>')
'알고리즘 > 연결리스트' 카테고리의 다른 글
| ABC 344 E번 복기 - 원소에 바로 접근할 수 있는 연결리스트 구현하는 법 (0) | 2024.03.14 |
|---|---|
| 파이썬을 이용한 연결리스트 기본 구현 테크닉 배우기 (0) | 2024.02.29 |