자료구조 | Singly Linked List | Linked List

singly Linked List가 동작하기 위해 필요한 클래스

 

링크드 리스트는 노드로 구성된다. 

노드는 노드 자신의 data와 다른 노드와 연결되는 link로 구성된다. 

단방향으로만 연결해주는 리스트 형태를 Singly linked list라고 한다. 

DLL Doubly linked list의 경우, left link와 right link를 모두 제공한다. 

 

스켈레톤 코드 : 함수가.. 많기도 하다. 

class Node:
    def __init__(self):
        pass

class SLL:
    def __init__(self):
        pass
    def isEmpty(self):
        pass
    def addFront(self, node):
        pass
    def addRear(self, node):
        pass
    def addSort(self, node):
        pass
    def delFind(self, node):
        pass
    def popFront(self, node):
        pass
    def popRear(self, node):
        pass
    def delAll(self):
        pass
    def view(self):
        pass
    def length(self):
        pass
    def reverse(self):
        pass
    def concat(self):
        pass
    def peekFront(self):
        pass
    def peekRear(self):
        pass

 

 

구현 완료~! :D

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

class SLL:
    def __init__(self):
        self.head = None
        self.rear = None
        self.count = 0
    def isEmpty(self):
        return self.head == None
    def addFront(self, node):
        tmp = self.head
        self.head = node
        node.link = tmp
        if self.count == 0:
            self.rear = self.head
        self.count += 1
    def addRear(self, node):
        tmp = self.rear
        self.rear = node
        self.rear.link = tmp
        if self.count == 0:
            self.head = self.rear
        self.count += 1
    def delFind(self, node):
        tmp = self.head 
        while True:
            if tmp == None:
                print("No such node")
                break
            elif tmp.data == node:
                del tmp
            else:
                tmp = tmp.link
        self.count -= 1
    def popFront(self):
        tmp = self.head.data
        self.head = self.head.link
        self.count -= 1
        return tmp
    def popRear(self):
        tmp = self.rear.data
        del tmp
        self.count -= 1
        return tmp
    def delAll(self):
        while True:
            if self.head == None:
                break
            tmp = self.head
            self.head = self.head.link
            del tmp
        self.count = 0
    def view(self):
        tmp = self.head
        while True:
            if tmp == None:
                break
            print(tmp.data)
            tmp = tmp.link
    def length(self):
        return self.count
    def concat(self, to):
        if self.head == None:
            self.head = to.head
        else:
            self.rear.link = to.head
    def peekFront(self):
        return self.head.data
    def peekRear(self):
        return self.rear.data
    def reverse(self):
        first = self.head
        second = third = None
        while first:
            third = second
            second = first
            first = first.link
            second.link = third
        self.head = second
    def addSort(self, node):
        # 비어있는 경우
        if self.count == 0 or \
            node.data <= self.head.data:
            self.addFront(node)
        elif node.data >= self.rear.data:
            self.addRear(node)
        else:
            tmp = self.head
            while True:
                if node.data <= tmp.link.data:
                    save = tmp.link
                    tmp.link = node
                    node.link = save
                else:
                    tmp = tmp.link
        self.count += 1
    def print(self):
        tmp = self.head
        while True:
            if tmp == None:
                break
            else:
                print(tmp.data)
                tmp = tmp.link
s = SLL()
for i in range(10):
    tmp = Node(i*100)
    s.addFront(tmp)
    
    
s.reverse()
s.print()