美文网首页Python_学习笔记
自己实现一个链表

自己实现一个链表

作者: Shun2018 | 来源:发表于2018-04-18 21:12 被阅读0次
    # 定义一个节点类Node
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    # 定义链表类LinkedList
    class LinkedList:
        def __init__(self):
            self.head = None
            self.tail = None
        
        # 定义链表的append方法(向链表尾部追加节点)
        def append(self, value):
            node = Node(value)
            if self.head is None:
                self.head = node
                self.tail = node
            else:
                self.tail.next = node
                self.tail = node
        
        # 定义链表的iter方法(迭代出链表的所有节点)
        def iter(self):
            cur = self.head
            if cur is None:
                print('Empty linkedList...')
                return
            while cur:
                yield cur.data
                cur = cur.next
    
        # 定义链表的insert方法(在指定索引处插入节点)
        def insert(self, idx, value):
            cur_idx = 0
            cur = self.head
            node = Node(value)
            if cur is None:
                if idx <= 0:
                    self.head = node
                    self.tail = node
                    return
            if idx < 0:
                print('insert idx too small')
                return
            while cur:
                if idx - 1 > cur_idx:
                    cur = cur.next
                    cur_idx += 1
                else:
                    break
            else:
                print('inserted idx too lager')
                return
            node.next = cur.next
            cur.next = node
            if node.next is None:
                self.tail = node
    
        # 定义链表的remove方法(删除指定索引处的节点)
        def remove(self, idx):
            cur_idx = 0
            cur = self.head
            if cur is None:
                raise Exception('Empty link list, can not remove elements.')
            if idx < 0:
                raise Exception('removed idx is too small...')
            if idx == 0:
                if cur.next is None:
                    self.head = None
                    self.tail = None
                else:
                    self.head = cur.next
                return
            while cur:
                if idx - 1 > cur_idx:
                    cur_idx += 1
                    cur = cur.next
                else:
                    break
            else:
                raise Exception('removed idx too lager')
            if cur.next is None:
                raise Exception('removed idx too lager')
            cur.next = cur.next.next
            if cur.next is None:
                self.tail = cur
    
    # 测试调用
    if __name__ == '__main__':
    
        link_list = LinkedList()
    
        for i in range(10):
            link_list.append(i)
        #
        # print(link_list.insert(0, 10))
        # # print('------')
        # print(link_list.insert(1, 11))
        # print('------')
        #
        # link_list.insert(-1, 20)
        link_list.remove(10)
    
        for node in link_list.iter():
            print(node)
    ···

    相关文章

      网友评论

        本文标题:自己实现一个链表

        本文链接:https://www.haomeiwen.com/subject/gfbbkftx.html