[자료구조💾] 5장 연결 리스트

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)

 

5.1 연결 리스트 개요

1) 연결 리스트의 종류

- 연결리스트 (linked list) : 노드들이 링크에 의해 순차적으로 연결된 자료구조

- 노드는 값을 저장하는 공간과 노드를 연결하는 링크(link)로 구성된다.

- 단일 연결 리스트 (singly linked list) : 노드들이 한 방향으로만 연결된 구조

- 이중 연결 리스트 (doubly linked llist) : 앞 뒤 양방향으로 연결된 구조

- 체인(chain) : 연결 리스트가 마지막 노드(마지막 노드 링크에 None이 저장됨.)에서 끝나는 구조

- 순환 연결 리스트 (circular linked list) : 마지막 노드가 첫 노드와 연결되는 구조

 

2) 연결 리스트의 표현

- 기본 단위 : 노드(node)

- 값을 저장하는 데이터(data) 필드, 노드를 연결하는 링크(link) 필드로 구성된다.

 

 

5.2 단일 연결 리스트

1) 개요

- 연결 리스트이 첫 노드를 가리키는 head 변수(리스트 포인터, list pointer), 마지막 노드를 가리키는 tail 변수

- 마지막 노드의 링크 값은 None

class Node:
    def __init__(self, item):
        self.data = item
        self.link = None

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

    def isEmpty(self):
        return not 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 = ", self.head.data , "T = ", self.tail.data)
        else:
            print("빈 리스트")
    
    def attach(self,item):
        node = Node(item)
        if not self.node:
            self.head = node
            self.tail = node
        elif self.tail:
            self.tail.link = node
            self.tail = node

 

2) 연결 리스트 노드 추가

1. 추가할 노드(node)를 생성한 후 data 필드에 값을 저장하고 link 필드를 None으로 초기화한다.
2. 연결 리스트가 빈 경우 (empty) : 노드(node)를 리스트 변수(head)에 저장하고 종료한다.
3. 연결 리스트가 비어 있지 않은 경우 (not empty) : 앞 노드(prev)를 탐색한다.
   1. prev가 존재하는 경우
      • prev의 link 필드 값을 노드(node)의 link 필드에 저장한다.
      • prev의 link 필드에 노드(node)를 저장하고 종료한다.
   2. prev가 존재하지 않는 경우 (리스트 맨 앞에 추가)
      • 노드(node)의 link 필드에 리스트 변수(head)를 저장한다.
      • 리스트 변수(head)에 노드(node)를 저장하고 종료한다. 

    def find(self, item):
        if not self.head:
            return None, None
        temp = self.head
        prev = None
        while temp:
            if temp.data == item:
                return prev, temp
            prev = temp
            temp = temp.link
        return None, None
    
    def insert(self, prev,item):
        if not self.head:
            return
        node = Node(item)
        if not prev:
            node.link = self.head
            self.head = node
            return
        before, temp = self.find(prev)
        if not temp:
            print("앞 노드 없음")
            return
        else:
            node.link = temp.link
            temp.link = node
            if not node.link:
                self.tail =node

 

3) 연결 리스트 노드 삭제

1. 리스트가 빈 경우 (empty) : 그대로 종료한다.
2. 리스트에 노드가 있는 경우 (not empty) : 삭제 노드(node)와 앞 노드(prev)를 탐색하고, 노드가 없으면 종료한다.
   1. prev가 있는 경우 (중간 노드 삭제) : prev의 link 필드에 node의 link 값을 저장한다.
   2. prev가 없는 경우 (첫 노드 삭제) : 리스트 변수(head)에 node의 link를 저장한다.
3. node를 삭제하고 종료한다.

    def del_find(self, item):
        if not self.head:
            print("빈 리스트")
            return
        prev, node = self.find(item)
        if not node:
            print("노드 없음")
            return
        if prev:
            prev.link = node.link
            print("노드 삭제됨.")
        else:
            if self.head == node:
                print("첫 노드 삭제됨.")
                self.head = node.link
        if node == self.tail:
            self.tail = prev
        del node

 

 

5.3 연결 리스트 연산

1) 리스트 길이 세기

- 연결 리스트의 길이 (length) : 노드의 수

- 반복문으로 리스트 변수에서부터 노드의 수를 계산하여 구현할 수 있다.

- 코드

    def length_list(self):
        count = 0
        temp = self.head
        while temp:
            count +=1
            temp = temp.link
        return count

 

2) 리스트 합치기

- 결합 (concatenation) : 두 개의 리스트를 연결하여 하나로 합치는 것

- 알고리즘

1. 앞 리스트가 빈 리스트라면 뒤의 리스트를 반환하고 종료한다.
2. 앞 리스트가 비어 있지 않다면
   1. 뒤의 리스트가 비어 있다면 앞의 리스트를 반환하고 종료한다.
   2. 뒤의 리스트가 비어 있지 않다면 앞 리스트의 마지막 노드를 탐색하여 뒤의 리스트를 연결하고 앞의 리스트를 반환한다.

- 코드

    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

lst1.head = lst2.concat(lst2.haed)

 

 

5.4 순환 연결 리스트

1) 순환 연결 리스트 (circular linked list)

- 마지막 노드의 링크가 None이 아니고 그 리스트의 첫 노드에 다시 연결되어 있다.

- 순환 연결 리스트의 길이 : 시작 노드로 다시 되돌아오는 순간이 전체 리스트를 모두 탐색한 시점

- 코드

class Node:
    def __init__(self, item):
        self.data = item
        self.link = None

class CircularList:
    def __init__(self, item):
        self.head = item
        self.link = None
    
    def isEmpty(self):
        return not self.head
    
    def add_rear(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("]")

        if self.head:
            print("H=", self.head.data, "T=", self.tail.data)
        else:
            print("빈 리스트")

 

2) 역순 연결 리스트 (reverse linked list)

- 주어진 리스트의 노드들을 반대 방향으로 연결된 리스트

- 알고리즘

1. 빈 리스트이거나 노드가 1개만 있는 경우, 리스트 변수(head)를 반환하고 종료한다.
2. 리스트 노드가 2개 이상인 경우, 추가 변수(second, third)를 사용하여 아래를 수행한다.
   1. third 변수가 second 노드를 가리키게 한다.
   2. second 변수가 first 노드를 참조하게 한다.
   3. first 변수를 다음 노드로 이동시킨다.
   4. second 노드의 링크에 third 값을 저장한다.
   5. first가 None이 아닐 때까지 2.1부터 반복한다.

- 코드 

    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

 

 

5.5 이중 연결 리스트

1) 이중 연결 리스트 (doubly linked list)

- 각 노드에서 앞 뒤 노드로 링크가 연결되어 있다.

- 이진 트리(binary tree)를 구현하는 데 활용된다.

- node == node.llink.rlink == node.rlink.llink

 

2) 이중 연결 리스트의 표현

- 일반적으로 헤드 노드(head)가 존재하는데, 헤드 노드의 링크는 리스트의 첫 노드와 마지막 노드를 가리키고, 데이터 필드에는 전체 노드의 수를 저장한다.

- 헤드 노드는 삭제할 수 없는 노드이며 항상 존재하므로 노드의 삽입, 삭제 연산이 편리하다.

class Node:
    def __init__(self, item):
        self.data = item
        self.rlink = None
        self.llink = None

class LinkedList:
    def __init__(self):
        self.head = Node(0)
        self.head.rlink = self.head
        self.head.llink = self.head
        
    def empty(self):
        return self.head.rlink == self.head

 

3) 이중 연결 리스트에 노드 추가

- 알고리즘

1. node의 llink가 prev 노드를 가리키도록 한다
2. node의 rlink가 prev 다음 노드를 가리키도록 한다.
3. prev 다음 노드의 llink가 node를 가리키도록 한다.
4. prev의 llink가 node를 가리키도록 한다.

- 코드

    def add(self, item):
        node = Node(item)
        self.head.data +=1
        if self.empty():
            node.llink = self.head
            node.rlink = self.head
            node.head.rlink = node
            self.head.llink = node
        else:
            node.llink = self.head.llink
            node.rlink = self.head
            self.head.llink.rlink = node
            self.head.llink = node

 

4) 이중 연결 리스트의 노드 삭제

- 알고리즘

1. 빈 리스트이거나 삭제할 노드(node)가 존재하지 않으면 종료한다.
2. 삭제 노드(node)가 head 노드가 아닐 경우, 앞 노드(node.llink)의 rlink에 node의 다음 노드(node.rlink)를 저장한다.
3. node의 다음 노드(node.llink)의 llink에 node의 앞 노드(node.llink)를 저장한다.
4. node를 삭제한다.

- 코드

    def find(self, item):
        temp = self.head.rlink
        while temp!=self.head:
            if temp.data == item:
                return temp
            temp = temp.rlink
        return None

    def delete(self, item):
        if self.empty():
            print("List Empty")
            return
        node = self.find(item)
        if not node:
            print("Not Found")
            return
        if node == self.head:
            print("head is not deleted")
            return
        self.head.data -= 1
        node.llink.rllink = node.rlink
        node.rlink.llink = node.llink
        del node