Python链表实现(转)

链表

链表是一种递归的数据结构,他或者为(null),或者是指向一个结点(node)的引用,该结点含有一个泛型的元素和一个指向另一条链表的引用. 如下图

链表图

链表中的基本要素：

1. 结点(也可以叫节点或元素)，每一个结点有两个域，左边部份叫值域，用于存放用户数据；右边叫指针域，一般是存储着到下一个元素的指针
2. head结点，head是一个特殊的结节，head结点永远指向第一个结点
3. tail结点，tail结点也是一个特殊的结点，tail结点永远指向最后一个节点
4. None，链表中最后一个结点指针域的指针指向None值，因也叫接地点，所以有些资料上用电气上的接地符号代表None

链表的常用方法：

1. LinkedList() 创建空链表，不需要参数，返回值是空链表
2. is_empty() 测试链表是否为空，不需要参数，返回值是布尔值
3. append(data) 在尾部增加一个元素作为列表最后一个。参数是要追加的元素，无返回值
4. iter() 遍历链表，无参数，无返回值，此方法一般是一个生成器
5. insert(idx,value) 插入一个元素，参数为插入元素的索引和值
6. remove(idx)移除1个元素，参数为要移除的元素或索引，并修改链表
7. size() 返回链表的元素数，不需要参数，返回值是个整数
8. search(item) 查找链表某元素，参数为要查找的元素或索引，返回是布尔值

python实现

# 结点对象
class Node:     ➊
    def __init__(self, data):
        self.data = data
        self.next = None

# 链表对象
class LinkedList:
    def __init__(self):    ➋
        self.head = None
        self.tail = None

    #is_empty方法检查链表是否是一个空链表，这个方法只需要检查head结点是否指向None即可
    def is_empty(self):    
        return self.head is None
    
    def append(self, data): ➌
        node = Node(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    # 遍历列表
    def iter(self):
        if not self.head:
            return
        cur = self.head
        yield cur.data
        while cur.next:
            cur = cur.next
            yield cur.data
  
    def insert(self, idx, value):  ➍
        cur = self.head
        cur_idx = 0
        if cur is None:             # 判断是否是空链表
            raise Exception('The list is an empty list')
        while cur_idx < idx-1:   # 遍历链表
            cur = cur.next
            if cur is None:   # 判断是不是最后一个元素
                raise Exception('list length less than index')
            cur_idx += 1
        node = Node(value)
        node.next = cur.next
        cur.next = node
        if node.next is None:
            self.tail = node
  
    def remove(self, idx):➎
        cur = self.head
        cur_idx = 0
        if self.head is None:  # 空链表时
            raise Exception('The list is an empty list')
        while cur_idx < idx-1:
            cur = cur.next
            if cur is None:
                raise Exception('list length less than index')
            cur_idx += 1
        if idx == 0:   # 当删除第一个结点时
            self.head = cur.next
            cur = cur.next
            return
        if self.head is self.tail:   # 当只有一个结点的链表时
            self.head = None
            self.tail = None
            return
        cur.next = cur.next.next
        if cur.next is None:  # 当删除的结点是链表最后一个结点时
            self.tail = cur
   
    # 遍历计数即可
    def size(self):
        current = self.head
        count = 0
        if current is None:
            return 'The list is an empty list'
        while current is not None:
            count += 1
            current = current.next
        return count
  
    def search(self, item):
        current = self.head
        found = False
        while current is not None and not found:
            if current.data == item:
                found = True
            else:
                current = current.next
        return found
  
if __name__ == '__main__':
    link_list = LinkedList()
    for i in range(150):
        link_list.append(i)
#    print(link_list.is_empty())
#    link_list.insert(10, 30)
  
#    link_list.remove(0)
  
    for node in link_list.iter():
        print('node is {0}'.format(node))
    print(link_list.size())
#    print(link_list.search(20))

➊ python用类来实现链表的数据结构，节点（Node）是实现链表的基本模块，每个节点至少包括两个重要部分。首先，包括节点自身的数据，称为“数据域”(也叫值域)。其次，每个节点包括下一个节点的“引用”(也叫指针).此节点类只有一个构建函数，接收一个数据参数，其中next表示指针域的指针，实例化后得到一个节点对象 node = Node(4)

image

➋ 初始化了head和tail节点，且两节点都指向None,link_list = LinkedList()

image

➌　既然要新增加节点，首先把Node类实例化得到一个node对象。这里有两种情况需要考虑:一是链表是一个空链表append一个节点,整个链表中就一个节点,此时head与tail都指向这个结点；二是当链表不是空链表append一个节点.
第二种情况重要讲:增加第二个节点的操作需要分两步完成，第一步：self.tail.next = node，即把上一个节点的next指针指向当前node；第二步：self.tail = node，把tail移动到node，如下图:

image

➍ 插入数据

image

1. 还要额外考虑两种情况：
2. 空链表时
3. 插入位置超出链表节点的长度时
4. 插入位置是链表的最后一个节点时，需要移动tail

➎ 删除数据 考虑以下几种情况

1. 空链表，直接抛出异常
2. 删除第一个节点时，移动head到删除节点的next指针指向的对象
3. 链表只有一个节点时，把head与tail都指向None即可
4. 删除最后一个节点时，需要移动tail到上一个节点
5. 遍历链表时要判断给定的索引是否大于链表的长度，如果大于则抛出异常信息

相关链接

这篇文章查看原链接,图片更多,也更容易理解,这里我只是转载过来做一个总结
https://facert.gitbooks.io/python-data-structure-cn/3.%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/3.10.%E4%BB%80%E4%B9%88%E6%98%AF%E9%98%9F%E5%88%97/
https://docs.lvrui.io/2016/07/20/Python%E4%B8%AD%E5%85%88%E8%BF%9B%E5%85%88%E5%87%BA%E9%98%9F%E5%88%97queue%E7%9A%84%E5%9F%BA%E6%9C%AC%E4%BD%BF%E7%94%A8/