교재 - 파이썬으로 배우는 자료구조(저자 유석종)

 

1. 순환 연결 리스트

`체인` : 연결 리스트의 마지막 노드의 링크에 None 값이 저장되어 있는 경우

`순환 연결 리스트` : 마지막 노드의 링크가 None이 아니고 그 리스트의 첫 노드에 다시 연결되어 있는 경우

순환 연결 리스트는 리스트 변수를 변경해도 여전히 전체 리스트가 연결 상태를 유지하는 특징이 있음.

 

 

2. 순환 연결 리스트의 길이

순환 연결 리스트는 링크가 None인 마지막 노드가 없기 때문에 시작 노드로 다시 되돌아 오는 순간이 전체 리스트를 모두 탐색한 시점임.

 

length_list 함수는 빈 리스트 여부를 검사.

빈 리스트가 아닌 경우는 첫 노드에서부터 temp를 이동시키면서 head 노드의 위치로 되돌아올 때까지 count 변수를 증가시킴.

 

# 5.7. 순환 연결 리스트의 길이
print("\n5.7. 순환 연결 리스트의 길이")
class Node:
    def __init__(self, item):
        self.data = item
        self.link = None

class CircularList:
    def __init__(self):
        self.head = self.tail = None

    def attach(self, item):     # 리스트 뒤에 노드 추가
        node = Node(item)
        if not self.head:
            self.head = node
            self.tail = node
        elif self.tail:
            self.tail.link = node
            self.tail = node
        node.link = self.head

    def length_list(self):      # 리스트 길이 세기
        if not self.head: return 0
        count = 0
        temp = self.head
        while True:
            count += 1
            temp = temp.link
            if temp == self.head: break
        return count

    def view(self):
        temp = self.head
        print("[", end=' ')
        while temp:
            print(temp.data, end=' ')
            temp = temp.link
            if temp is self.head: break
        print("]", end=' ')
        if self.head:
            print("  H=%d T=%d" % (self.head.data, self.tail.data))
        else: print("빈 리스트")

lst = CircularList()
for item in [200, 100, 150, 200, 300, 250]:
    lst.attach(item)
lst.view()
print("리스트 길이 =", lst.length_list())
# 출력 결과
5.7. 순환 연결 리스트의 길이
[ 200 100 150 200 300 250 ]   H=200 T=250
리스트 길이 = 6

 

 

 

 

3. 역순 연결 리스트

`역순 연결 리스트` : 리스트의 노드들을 반대 방향으로 연결한 리스트.

예를 들어 head -> 100 -> 200 -> 300 이라면

역순 연결리스트는 head -> 300 -> 200 -> 100

 

[ 알고리즘 | 역순 연결 리스트 ]

1. 빈 리스트이거나 노드가 1개인 경우 : head 변수를 반환하고 종료한다.

2. 리스트 노드가 2개 이상인 경우

    (1) third 변수가 second 노드를 가리키게 된다.

    (2) second 변수가 first 노드를 참조하게 된다.

    (3) first 변수를 다음 노드로 이동시킨다.

    (4) second 노드의 링크에 third 값을 저장한다.

    (5) first 가 Nonde 이 아닐 때까지 2-(1)번부터 반복한다.

 

이 알고리즘의 시간 복잡도는 리스트의 길이(O(N))에 비례함.

 

아래 프로그램 5.8.의 reverse 함수에 역순 리스트 알고리즘이 구현되어 있음. 실행 결과를 보면 리스트의 연결 순서가 반대로 되어 있는 것을 확인할 수 있음.

# 5.8. 역순 연결 리스트
print("\n5.8. 역순 연결 리스트")
class Node:
    def __init__(self, item):
        self.data = item
        self.link = None

class SinglyLinkedlist:
    def __init__(self):
        self.head = self.tail = None

    def view(self):
        temp = self.head
        print("[", end=' ')
        while temp:
            print(temp.data, end=' ')
            temp = temp.link
        print("]", end=' ')
        if self.head:
            print("  H=%d T=%d" % (self.head.data, self.tail.data))
        else: print("빈 리스트")

    def attach(self, item):
        node = Node(item)
        if not self.head:
            self.head = node
            self.tail = node
        elif self.tail:
            self.tail.link = node
            self.tail = node

    def reverse(self):
        first = self.head
        second = third = None
        self.tail = self.head
        while first:
            third = second
            second = first
            first = first.link
            second.link = third
        self.head = second

lst1 = SinglyLinkedlist()
for item in [200, 100, 150, 200, 300, 250]:
    lst1.attach(item)

lst1.view()
lst1.reverse()
lst1.view()
# 실행 결과
5.8. 역순 연결 리스트
[ 200 100 150 200 300 250 ]   H=200 T=250
[ 250 300 200 150 100 200 ]   H=250 T=200

 

 

헷갈렸던 점

reverser() 의 마지막 코드 self.head = second 부분.

: 역순 리스트 알고리즘을 통해 second가 현재까지 뒤집힌 리스트의 맨 앞이 됨.

원래 : head → [200] → [100] → [150] → ... → [250] → None
뒤집고 나면 : head → [250] → [300] → ... → [200] → None

 

루프 끝나면

[250] → [300] → ... → [200]

이런 상태. 

 

루프 시작할 때

first = self.head
self.tail = self.head

이랬으므로 self.head는 여전히 [200]을 가리키는 중. 그래서 역순으로 잘 뒤집어도 head는 여전히 처음 노드니까 self.head = second를 통해 head를 새로 바뀐 리스트의 첫번째 노드로 바꿔줌.

 

 

 

 

티스토리툴바