数据结构与算法单链表实现

#单链表实现(链表)    #要学的重点才从这里刚刚开始
class Node(object):
    def __init__(self, value = None, next = None):
        self.value, self.next = value, 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 append(self, value):
        if self.maxsize is not None and len(self) > self.maxsize:
            raise Exception('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 __iter__(self):
        for node in self.iter_node():
            yield node.value

    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
                del curnode
                self.length -= 1
                return 1
            else:
                prevnode = curnode
        return -1
    def find(self, value):  #O(n)
        index = 0
        for node in self.iter_node():
            if node.value == value:
                return index
            index += 1
        return -1

    def popleft(self):  #O(1)
        if self.root.next is None:
            raise Exception('pop from empty LinkedList')
        headnode = self.root.next
        self.root.next = headnode.next
        self.length -= 1
        value = headnode.value
        del headnode
        return value

    def clear(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)

    assert len(ll) == 3
    assert ll.find(2) == 2
    assert ll.find(3) == -1

    ll.remove(0)
    assert len(ll) == 2
    assert ll.find(0) == -1

    assert list(ll) == [1, 2]

    ll.appendleft(0)
    assert list(ll) == [0, 1, 2]
    assert len(ll) == 3

    headvalue = ll.popleft()
    assert headvalue == 0
    assert len(ll) == 2
    assert list(ll) == [1, 2]

    ll.clear()
    assert len(ll) == 0

使用pytest测试的结果是：

数据结构与算法单链表实现

1 passed，说明该单链表类是可成功实现的，下面指出该类每个method的重点实现语句和思想：

__len__:计算单链表长度，没啥好说的。

append:

单链表通常有个root(head),有个tailnode.root不存放value，只存放地址，一个node由value和next（指针）组成。

在末位追加值，即为

if tailnode is None:
    self.root.next = node    #单链表为空时，直接放在root.next
else:
    tailnode.next = node
self.tailnode = node

appendleft:同append相反，在头部追加，把原来的root.next赋值给headnode,再把后来想要追加的node的node.next = headnode就好了，这就是appendleft的核心

iter_node:使用yield表达式，返回每一个节点（包括了value和next）
__iter__:只返回value
remove:需要两个中间变量，然后是用a.next = b.next的方式删除某一节点

find:需要用到iter_node()来找到相同的value值，返回其index

popleft:删除最左边的节点，最主要先把root.next = headnode,然后root.next = headnode.next，这就是最主要的，到此可以删除headnode了，但pop操作是要返回value值的，所以在del headnode之前，把value提取出来以便return，value = headnode.value

clear:遍历一遍，del node就完事了。

到此单链表的基础知识也就了解了，下次好好总结下双端链表。

数据结构与算法 单链表实现

相关推荐

数据结构与算法单链表实现