python实现链表

之前只是介绍过链表这种数据结构，但是，没有进行详细的讲解，虽然这种数据结构在很多时候，特别是在读取元素的时候，并不是显得很高效，但是仍然值得我们学习，链表问题也是面试中常见的问题，比如：链表的逆置，因此深入的学习这种数据结构很有必要。

链表

链表是实现了数据之间保持逻辑顺序，但存储空间不必按顺序的方法。

基本概念

1.节点：每一个节点有两个域，左边部份叫值域，用于存放用户数据；右边叫指针域，一般是存储着到下一个元素的指针。
2.head节点：head是一个特殊的节点，head节点永远指向第一个节点。
3.tail节点：tail节点也是一个特殊的节点，tail节点永远指向最后一个节点。
4.None：链表中最后一个节点指针域的指针指向None值。

常用方法：

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

#节点类
python用类来实现链表的数据结构，节点类中包含两个属性，数据和指针：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

此节点类只有一个构建函数，接收一个数据参数，其中next表示指针域的指针，实例化后得到一个节点对象，如下：

node = Node(4)

备注：此节点对象数据为4，指针指向None。

链表类

创建空链表，不需要参数，返回值是空链表：

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

此类实例后会生成一个链表对象，初始化了head和tail节点，且两节点都指向None，实例化代码如下：

link_list = LinkedList()

is_empty方法

is_empty方法检查链表是否是一个空链表，这个方法只需要检查head节点是否指向None即可：

def is_empty(self):
        return self.head is None

#append方法
append方法表示增加元素到链表，这和insert方法不同，前者使新增加的元素成为链表中第一个节点，而后者是根据索引值来判断插入到链表的哪个位置。代码如下：

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

iter方法实现

iter方法用来遍历链表，分两种情况：
1.空链表
2.遍历链表时从head开始，直到一个节点的next指向None结束，代码如下：

def iter(self):
        if not self.head:
            return
        cur = self.head
        yield cur.data
        while cur.next:
            cur = cur.next
            yield cur.data

备注：使用局部变量cur指向head,把对应的data yield出来，再对cur的next指针指向的对象做while循环，直到next指向None，这样就遍历了链表。

insert方法

采用遍历的方式找到需要插入，改变对应的指针域所指的位置：

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

#remove方法
remove方法接收一个idx参数，表示要删除节点的索引，此方法要考虑以下几种情况：
1.空链表，直接抛出异常
2.删除第一个节点时，移动head到删除节点的next指针指向的对象
3.链表只有一个节点时，把head与tail都指向None即可
4.删除最后一个节点时，需要移动tail到上一个节点
5.遍历链表时要判断给定的索引是否大于链表的长度，如果大于则抛出异常信息

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

size方法

size函数不接收参数，返回链表中节点的个数，遍历链表，用一个累加器count来计算节点的个数：

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

find方法

find函数接收一个item参数，表示查找节点中数据域的值。find方法遍历链表，每到一个节点把当前节点的data值与item作比较：

def find(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