자료구조 6장 | Linked List | 숙명여대 학점교류

학점교류로 듣는 숙명여대 자료구조

 

day 4. 2021.12.27. 월

 

---

Introduction

Singly linked list

linked stack and queue

deque

circular list

doubly linked list

---

Introduction

 

list

a list is a collection data type that has a sequence of elements

ex) days of week, months of year

 

linked list

elements are physically distributed in memory

logically sequential by link pointer # link 변수

variable list size

easy to Create, insert, or delete a list node

list management overhead

 

** 파이썬에서는? 

파이썬의 리스트와 파이썬의 연결 리스트의 경우, 

해당사항 없음. (정적 배열이 아니기 때문)

link를 이용해서 원소를 관리한다. 

 

link representation

data field : node information

link field : a reference which connects with next node

* SLL Singly linked list

* DLL doubly linked list

 

SLL - operations

• init
• isEmtpy

 

• add_front
• add_rear
• add_sort

 

• del_find
• pop_front
• pop_rear
• del_all

 

• view
• length
• reverse
• concat

 

• peek_front : 값을 참조만 한다
• peek_rear 

 

 

 

Singly linked list

* node

* add_sort

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.rear = None
    def isEmpty(self):
        return not self.head # head가 None
    def add_sort(self, item):
        # 조건 : 이미 정렬된 linked list여야 한다. 
        # 작은 건 건너뛰고
        # 큰 거 에서는 멈춰야 한다. 
        node = Node(item)
        if not self.head: # empty list
            self.head = node
            self.rear = node
            return
        else:
            temp = self.head
            prev = None
            while temp:
                if item > temp.data:
                    prev = temp
                    temp = temp.link
                elif item == temp.data:
                    print("Duplicate item")
                    # 중복되는 경우 거부한다. 
                    return
                else:
                    # item < temp.data
                    # node를 찾음
                    node.link = temp
                    if prev: prev.link = node # 중간에 들어감
                    else: self.head = node # 가장 앞에 들어감
                    return
        # 너무 커서
        # 맨 뒤에 붙이는 경우이다
        prev.link = node
        self.tail = node

        node.data

 

* del_find(self, item)

경우가 매번 다르다

def find 함수는 미리 정의되어있다. 

이 함수에서는 linked list를 정리해주는 것이 중심이다. 

list 단원에서는 항상 모든 경우를 나열해보아야 한다. *** case

 

    def del_find(self, item):
        if not self.head:
            print("List EMpty")
            return
        prev, node = self.find(item)
        if not node:
            print("Not Found")
            return
        if prev:
            prev.link = node.link
            print("Node is deleted")
        else:
            if self.head == node:
                print("Head is deleted")
                self.head = node.link
        if node == self.tail:
            self.tail = prev
        del node

 

* find

    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 # temp = temp.next와 같다
        return None, None

 

* view

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, "R=",self.rear.data)
    else:
        print("List is Empty")

클래스..

dot 연산자를 쓴다. 각 노드의 데이터를 저장하는 게 관건

SLL는 Head -> Rear(tail)

 

 

* length

number of node

rear가 있으면 좋은 점은? 

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

lst = SinglyLinkedList() # 객체
for item in range(10):
    lst.add_sort(item)
lst.view()
print("List length = ", lst.length())

head가 0이라면? 

head가 없다면? dangling reference 허상 참조

node를 참조하는 포인터가 다른 곳을 가리키면, 이 노드에 접근할 방식이 없어진다. 

임시 변수를 써준다. 

 

---