연결 리스트 - 연결 리스트 연산

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

---

1. 리스트의 길이 세기

연결 리스트의 길이(length)는 노드의 수를 의미함. 반복문으로 리스트 변수(head)에서부터 노드의 수를 계산하여 구현할 수 있음. 노드가 존재하면 count 변수를 1씩 증가시키고, 링크가 None인 마지막 노드에 도달하면 개수 세기를 멈춤.

 

아래 프로그램 5.5.는 연결 리스트를 생성하고 리스트 노드의 수를 계산함.

print("5.5. 연결 리스트의 길이")
class Node:
    def __init__(self,item):
        self.data = item
        self.link = None    # 다음 노드를 가리키는 링크

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

    def length_list(self):
        count = 0
        temp = self.head
        while temp:     # temp가 None이 아닐때까지(노드가 있을 때까지)
            count += 1
            temp = temp.link
        return count

    def view(self):
        temp = self.head
        print("[", end=' ')
        while temp:
            print(temp.data, end=' ')
            temp = temp.link
        print("]", end=' ')
        if self.head:
            print("H=", self.head.data, "T=", 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       # tail의 link에 새 노드를 연결
            self.tail = node            # tail이 새 노드를 가리킴

lst = SinglyLinkedlist()
for item in [100, 200, 300, 400, 500, 600]:
    lst.attach(item)
lst.view()
print("List length =", lst.length_list())

# 출력 화면
5.5. 연결 리스트의 길이
[ 100 200 300 400 500 600 ] H= 100 T= 600
List length = 6

 

 

 

 

---

2. 리스트 합치기

리스트 결합 : 두 개의 리스트를 연결하여 하나로 합치는 것.

(원래 결합은 두 개의 문자열을 합치는 연산)

 

다음은 리스트 합치기 연산의 알고리즘임.

[ 알고리즘 | 연결 리스트 합치기 ]

1. 앞 리스트(list)가 빈 리스트라면 뒤 리스트(list2)를 반환하고 종료한다.

2. list1가 빈 리스트가 아닌 경우

    (1) list2가 빈 리스트이면, list1을 반환하고 종료한다.

    (2) list2가 빈 리스트가 아니면, list1의 마지막 노드를 탐색하여 list2를 연결한 후 list1을 반환하고 종료한다.

 

list1과 list2를 합치는 경우, list1의 마지막 노드가 주어지지 않는다면 결합 연산의 시간 복잡도는 list1의 길이에 비례함. 이 알고리즘은 아래 프로그램 5.6.의 concat 함수에 구현되어 있음. attach 함수로 리스트를 생성하고, view 함수로 노드를 출력함. 실행 결과에서 2개의 리스트가 하나로 연결되어 있는 것을 알 수 있음.

 

# 5.6. 연결 리스트 합치기
print("\n5.6. 연결 리스트 합치기")
class Node:
    def __init__(self, item):
        self.data = item
        self.link = None

class SinglyLinkedlist:
    def __init__(self):
        self.head = None
        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

    def concat(self, second):
        if not self.head:       # 앞 리스트가 빈 경우
            return second
        elif second:            # 두 리스트가 모두 노드가 있는 경우
            temp = self.head
            while temp.link:    # 앞 리스트의 마지막 노드 찾기
                temp = temp.link
            temp.link = second
        return self.head

    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("빈 리스트")

lst1 = SinglyLinkedlist()
lst2 = SinglyLinkedlist()
for item in [100, 200, 300]:
    lst1.attach(item)
lst1.view()
for item in [400, 500, 600]:
    lst2.attach(item)
lst2.view()
lst1.head = lst1.concat(lst2.head)
lst1.tail = lst2.tail
lst1.view()

# 출력 결과
5.6. 연결 리스트 합치기
[ 100 200 300 ]   H=100 T=300
[ 400 500 600 ]   H=400 T=600
[ 100 200 300 400 500 600 ]   H=100 T=600

 

 

 

---