单向链表-白红宇

单向链表

阅读量：433 次

发布时间：2019-03-06

本文共 1801 字，大约阅读时间需要 6 分钟。

class Node(object):
    def __init__(self,value=None,next=None):
        self.value = value
        self.next = next
class LinkedList(object):
    def __init__(self,maxsize=None):
        self.maxsize = maxsize
        self.root = Node()
        self.length = 0
        self.tailnode = None
    def __len__(self):
        return self.length
    
    def __iter__(self):
        for node in self.iter_node():
            yield node.value
    
    def append(self,value):
        if self.maxsize is not None and len(self) > self.maxsize:
            raise Exception('list is full')
        node = Node(value)
        tailnode = self.tailnode
        if tailnode is None:
            self.root.next = node
        else:
            tailnode.next = node
        self.tailnode = node
        self.length += 1
    def appendleft(self,value):
        headnode = self.root.next
        node = Node(value)
        self.root.next = node
        node.next = headnode
        self.length += 1
    def iter_node(self):
        curnode = self.root.next
        while curnode is not self.tailnode:
            yield curnode
            curnode = curnode.next
        yield curnode
    def remove(self,value):
        prevnode = self.root
        curnode = self.root.next
        for curnode in self.iter_node():
            if curnode.value == value:
                prevnode.next = curnode.next
                if curnode is self.tailnode:
                    self.tailnode = prevnode
                del curnode
                self.length -= 1
                return 1
            else:
                prevnode = curnode
        return -1
    def finde(self,value):
        index = 0
        for node in self.iter_node():
            if node.value == value:
                return index
            index += 1
        return -1
    def popleft(self):
        if self.root.next is None:
            raise Exception('POP is None!!')
        headnode = self.root.next
        self.root.next = headnode.next
        self.length -= 1
        value = headnode.value
        del headnode
        return value
    def claer(self):
        for node in self.iter_node:
            del node
        self.root.next = None
        self.length = 0
def test_linkedlist():
    ll = LinkedList()
    ll.append(0)
    ll.append(1)
    ll.append(2)
    ll.append(3)
    ll.append(4)
    ll.append(5)
    assert len(ll) == 6
    assert ll.finde(10) == -1
    ll.remove(5)
    assert len(ll) == 5
    assert list(ll) == [0,1,2,3,4]