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

$$python实现单链表$$

难点

1.节点构造

class _Node:        def __init__(self, e=None, node_next=None):            self.e = e            self.next = node_next

2.add

def add(self, index, e):        if index < 0 or index > self._size:            raise ValueError('Add failed. Illegal index.')        prev = self._dummy_head        for i in range(index):            prev = prev.next        node = self._Node(e)        node.next = prev.next        prev.next = node        self._size += 1

3.delete

def remove(self, index):        if index < 0 or index >= self._size:            raise ValueError('Remove failed. Illegal index.')        prev = self._dummy_head        for i in range(index):            prev = prev.next        ret = prev.next        prev.next = ret.next        ret.next = None        self._size -= 1        return ret.e

练习三部曲之一

class LinkedList:    # 1.节点构造    class _Node:        def __init__(self, e=None, node_next=None):            self.e = e            self.next = node_next        def __str__(self):            return str(self.e)        def __repr__(self):            return self.__str__()    # 2.成员构造    def __init__(self):        self._dummy_head = self._Node()        self._size = 0            # 3.魔法方法    def __str__(self):        curr = self._dummy_head.next        data = []        while curr:            data.append(str(curr.e))            curr = curr.next        return '(Head) ' + ' -> '.join(data) + ' (Tail)'    def __repr__(self):        return self.__str__()    # 4.返回大小    def get_size(self):        return self._size    # 5.判空    def is_empty(self):        return self._size == 0    # 6.增    def add(self, index, e):        if index < 0 or index > self._size:            raise ValueError('Add failed. Illegal index.')        prev = self._dummy_head        for i in range(index):            prev = prev.next        node = self._Node(e)        node.next = prev.next        prev.next = node        self._size += 1            def add_first(self, e):        self.add(0, e)    def add_last(self, e):        self.add(self._size, e)    # 7.删    def remove(self, index):        if index < 0 or index >= self._size:            raise ValueError('Remove failed. Illegal index.')        prev = self._dummy_head        for i in range(index):            prev = prev.next        ret = prev.next        prev.next = ret.next        ret.next = None        self._size -= 1        return ret.e    def remove_first(self):        return self.remove(0)    def remove_last(self):        return self.remove(self._size - 1)            # 8.改    def setter(self, index,e):        if index < 0 or index >= self._size:            raise ValueError('Set failed. Illegal index.')        curr = self._dummy_head.next        for i in range(index):            curr = curr.next        curr.e = e            # 9.查    def get(self, index):        if index < 0 or index >= self._size:            raise ValueError('Get failed. Illegal index.')        curr = self._dummy_head.next        for i in range(index):            curr = curr.next        return curr.e    def get_first(self):        return self.get(0)    def get_last(self):        return self.get(self._size - 1)        def contains(self, e):        curr = self._dummy_head.next        while curr:            if curr.e == e:                return True            curr = curr.next        return False

练习三部曲之二

class LinkedList:    # 1.节点构造    class _Node:        def __init__(self, e=None, node_next=None):        def __str__(self):        def __repr__(self):    # 2.成员构造    def __init__(self):    # 3.魔法方法    def __str__(self):    def __repr__(self):    # 4.返回大小    def get_size(self):    # 5.判空    def is_empty(self):    # 6.增    def add_first(self, e):    def add_last(self, e):    def add(self, index, e):    # 7.删    def remove(self, index):    def remove_first(self):    def remove_last(self):        # 8.改    def setter(self, index,e):    # 9.查    def get(self, index):    def get_first(self):    def get_last(self):    def contains(self, e):

练习三部曲之三

class LinkedList:    # 1.节点构造    # 2.成员构造    # 3.魔法方法    # 4.返回大小    # 5.判空    # 6.增    # 7.删    # 8.改    # 9.查