链表（三）

我们知道顺序表存储数据时，需要一块连续的内存空间，插入删除时要进行数据搬迁，并不是那么灵活。

而现在就有这么一种数据结构， 存储时不需要是连续的内存空间存储，而是可以单独的内存空间存储。每个内存空间之间以 链条形式串起来，充分利用了计算机的内存空间，这就是 链表。

链表定义

链表是一种常见的数据结构，也是一种线性表，不像顺序表一样连续存储数据，而是每个节点里存储了下一个节点的地址，类似于下面这样：

链表结构

3.1 单链表

单链表又称单向链表，顾名思义它只有一个方向。单链表每个节点包含两个域：

• 信息域：又称元素域，存储数据用
• 链接域：指向下一个节点地址，最后一个节点链接域指向 None

image

变量 p 指向头节点，需要注意的是单链表操作都是从头节点开始的。

---

Python 变量标识本质

Python 中存储一个变量，计算机会为其分配两块内存空间。一部分用来存储变量本身，另一部分用来存储数据，变量通过 标识（类似于指针） 指向数据。

那么 a, b = b, a 其实就是改变变量的指向而已：

image

---

节点实现

class Node:
    def __init__(self, elem):
        self.elem = elem        # 存储数据
        self.next = None        # 下一个节点标识

单链表操作

• is_empty()：判断链表是否为空
• length() ：返回链表的长度
• travel() ：遍历
• add(item) ：在头部添加一个节点
• append(item)： 在尾部添加一个节点
• insert(pos, item)： 在指定位置pos添加节点
• remove(item)：删除一个节点
• search(item) ：查找节点是否存在

单链表实现

1、判断链表是否为空、链表长度、遍历链表

class SingleLinkList:
    def __init__(self, node=None):
        self.__head = node  # 表示一个节点
        
    def is_empty(self):
        """是否为空"""
        return self.__head = None
    
    def travel(self):
        """遍历所有元素"""
        cur = self.__head        # cur 初始时指向头节点
        while cur != None:
            print(cur.elem, end=' ')
            cur = cur.next      # 将cur后移一个节点
        print('')
        
    def length(self):
        """链表长度"""
        # cur 游标，用来移动遍历节点
        cur = self.__head
        count = 0   # 记录数量
        while cur != None:
            count += 1
            cur = cur.next
        return count

• self.__head 表示头节点，判断是否为空，只需判断表达式 self.__head=None 的值即可，若头结点为 None，链表即为空
• 遍历元素：cur 为向后移动的游标，初始遍历时指向头节点 self.__head，最后一个节点的 next 节点为 None，因此只要不为 None，就一直移动
• 链表长度：和遍历元素原理一致，只不过多了一个 count 用来记录 cur 移动的数量

image

2、头部插入、尾部插入、任意位置插入：

头部插入 任意位置插入

def add(self, item):
    """头部插入，头插法（item：要插入的元素）"""
    node = Node(item)   # 创建一个节点以保存 item
    node.next = self.__head     # 新节点的 next 指向头节点，即 self.__head 指向的地方
    self.__head = node          # 将头节点 self._head  指向新节点
    
def append(self, item):
    """尾部插入，尾插法"""
    node = Node(item)
    # 链表是否为空，将 self.__head  指向新节点 
    if self.is_empty():
        self.__head = node
    # 不为空，则找到尾部，将尾节点的next指向新节点
    else:
        cur = self.__head
        while cur.next != None:     # 当 cur.next == None 时，说明已经找到了最后一个元素，那就跳出循环
            cur = cur.next
        cur.next = node     # 将尾节点的next指向新节点
        
def insert(self, pos, item):
    """pos：位置，item：要插入的元素，任意位置插入"""
    # 空链表，即插入在第一个，将 self.__head 指向新节点，也就是头插法
    if pos <= 0:
        self.add(item)
    elif pos > (self.length - 1):   # 尾插法
        self.append(item)
    else:                   # 中间插入
        pre = self.__head       # pre 用来指定 pos 的前一个位置 pos-1，初始从头开始移动到指定位置
        count = 0
        while count < (pos-1):
            count += 1
            pre = pre.next
        node = Node(item)
        node.next = pre.next        # 先将新节点 node 的 next 指向插入位置的节点（保证数据不丢失）
        pre.next = node     # 将插入位置的前一个节点的 next 节点指向新节点

3、删除节点

删除节点

    def remove(self, item):
        cur = self.__head
        pre = None
        while cur != None:
            # 找到指定元素
            if cur.elem == item:
                # 如果要删除的是第一个节点
                if cur == self.__head:
                    self.__head = cur.next      # 将头指针指向头节点的后一个节点
                else:
                    # 将删除位置的前一个节点的 next 指向删除位置的后一个节点
                    pre.next = cur.next
                    # cur.next = None
                break
            else:
                pre = cur
                cur = cur.next      # 继续移动节点

4、查找节点是否存在：

def search(self, item):
    """
        搜索、查找
        :return:
        """
    cur = self.__head
    while cur != None:
        if cur.elem == item:
            return True
        else:
            cur = cur.next
            return False

5、测试：

if __name__ == '__main__':
    s1 = SingleLinkList()
    print(s1.is_empty())
    print(s1.length())

    s1.append(1)
    print(s1.is_empty())
    print(s1.length())

    s1.append(2)
    s1.add(8)
    s1.append(3)
    s1.append(4)

    s1.insert(-1, 9)
    s1.travel()

    s1.insert(10, 200)
    s1.travel()

    s1.remove(100)
    s1.travel()

运行结果如下：

True
0
False
1
9 8 1 2 3 4 
9 8 1 2 3 4 200 
9 8 1 2 3 4 200 

---

链表与顺序表对比

• 链表：
  • 不能随机访问，只能顺序访问，每个节点还多了一个指针域，因此空间消耗大。但是它能够将零散的空间链接起来，比较灵活
  • 查找慢、插入和删除慢（头部和尾部快）
  • 虽然中间插入/删除也是 O(n)，但是主要是遍历元素
• 顺序表：
  • 支持随机访问、顺序访问，访问速度快，不够灵活
  • 查找快、插入和删除慢（除了头部和尾部）
  • 中间插入/删除需要将元素往后或往前移动

链表与顺序表的各种操作复杂度如下所示：

操作	链表	顺序表
访问元素	O(n)	O(1)
在头部插入/删除	O(1)	O(n)
在尾部插入/删除	O(n)	O(1)
在中间插入/删除	O(n)	O(n)

3.2 双向链表

双向链表又称双链表，比之单链表多了一个前驱节点（前驱、后继节点）。

双向链表结构：

双向链表结构

操作

• is_empty()：判断链表是否为空
• length() ：返回链表的长度
• travel() ：遍历
• add(item) ：在头部添加一个节点
• append(item)： 在尾部添加一个节点
• insert(pos, item)： 在指定位置pos添加节点
• remove(item)：删除一个节点
• search(item) ：查找节点是否存在

实现

class Node(object):
    def __init__(self, item):
        self.elem = item
        self.next = None
        self.pre = None


class DoubleLinkList(object):
    """
    is_empty()、append()、insert()、remove()、length()
    """

    def __init__(self, node=None):
        self.__head = node  # 头节点

    def is_empty(self):
        # if self.__head == None:
        #     return True
        return self.__head == None

    def length(self):
        cur = self.__head
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        # 遍历
        cur = self.__head
        while cur != None:
            print(cur.elem, end=' ')
            cur = cur.next
        print('')

    def add(self, item):
        """
        头部添加
        :return:
        """
        node = Node(item)
        node.next = self.__head
        # self.__head.pre = node
        self.__head = node
        node.next.pre = node

    def append(self, item):
        # 尾部插入，尾插法
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.pre = cur

    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            cur = self.__head
            count = 0
            while count < pos:
                count += 1
                cur = cur.next
            node = Node(item)
            node.next = cur
            node.pre = cur.pre
            cur.pre.next = node
            cur.pre = node

    def remove(self, item):
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                # 头节点
                if cur == self.__head:
                    self.__head = cur.next
                    # 只有一个节点
                    if cur.next:
                        cur.next.pre = None
                else:
                    cur.pre.next = cur.next
                    # 最后一个节点为的 next 指向 None，None 没有 pre 和 next
                    if cur.next:
                        cur.next.pre = cur.pre
                break
            else:
                cur = cur.next



    def search(self, item):
        """
        搜索、查找
        :return:
        """
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False


if __name__ == '__main__':
    s1 = DoubleLinkList()
    print(s1.is_empty())
    print(s1.length())

    s1.append(1)
    print(s1.is_empty())
    print(s1.length())

    s1.append(2)    
    s1.add(8)
    s1.append(3)
    s1.append(4)    # 8 1 2 3 4 

    s1.insert(-1, 9)  # -1 当第一个处理，9 8 1 2 3 4 
    s1.travel()

    s1.insert(10, 200)   # 9 8 1 2 3 4 200
    s1.travel()

    s1.remove(200)      # 9 8 1 2 3 4 
    s1.travel()

3.3 单向循环链表

与单链表相比，单向循环链表最后一个节点不再指向 None，而是指向第一个节点，其结构如下：

单向循环链表结构

操作

操作

• is_empty()：判断链表是否为空
• length() ：返回链表的长度
• travel() ：遍历
• add(item) ：在头部添加一个节点
• append(item)： 在尾部添加一个节点
• insert(pos, item)： 在指定位置pos添加节点
• remove(item)：删除一个节点
• search(item) ：查找节点是否存在

实现

1、是否为空、遍历即链表长度：

class Node(object):
    def __init__(self, item):
        self.elem = item
        self.next = None


class SingleCycleLinkList(object):
    """
    is_empty()、append()、insert()、remove()、length()
    """
    def __init__(self, node=None):
        self.__head = node        # 头节点

    def is_empty(self):
        # if self.__head == None:
        #     return True
        return self.__head == None

    def travel(self):
        # 遍历
        if self.is_empty():
            return
        cur = self.__head
        # cur.next = self.__head 表示是最后一个元素
        while cur.next != self.__head:
            print(cur.elem, end=' ')
            cur = cur.next
        # 最后一个元素没在循环中，单独取出
        print(cur.elem)

    def length(self):
        if self.is_empty():
            return 0
        cur = self.__head
        count = 1
        # cur.next = self.__head 表示是最后一个元素，所以 count 要从 1 开始，或者 return count+1
        while cur != self.__head:
            count += 1
            cur = cur.next
        return count

2、头插法、尾插法及任意位置插入：

任意位置插入

    def add(self, item):
        """
        头部添加
        :return:
        """
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node  # 若链表为空，链表 next 指向自己
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            node.next = self.__head
            self.__head = node
            cur.next = self.__head  # 循环到链表最后一个元素，指向头节点

    def append(self, item):
        # 尾部插入，尾插法
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            node.next = self.__head
            cur.next = node

    def insert(self, pos, item):
        """pos 从 0 开始"""

        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos - 1):
                count += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node

3、搜索：

def search(self, item):
    """
        搜索、查找
        :return:
        """
    if self.is_empty():
        return False
    cur = self.__head
    while cur.next != self.__head:
        if cur.elem == item:
            return True
        else:
            cur = cur.next
            # 推出循环，cur 停留在最后一个节点上
            if cur.elem == item:
                # 若要找的元素恰好是最后一个元素
                return True
            return False

4、移除：

image

    def remove(self, item):
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            # 找到要移除的节点
            if cur.elem == item:
                # 要找的节点为头节点
                if cur == self.__head:
                    real = self.__head
                    # 循环找尾节点
                    while real.next != self.__head:
                        real = real.next
                    self.__head = cur.next
                    real.next = self.__head
                else:
                    pre.next = cur.next
                break
            else:
                # 继续往后移动
                pre = cur
                cur = cur.next

        # 退出循环没有找到节点，此时 cur 停留在最后一个节点上
        if cur.elem == item:
            if cur == self.__head:
                # 若只有一个节点元素
                self.__head = None
            else:
                pre.next = self.__head

测试

if __name__ == "__main__":
    ll = DLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print "length:",ll.length()
    ll.travel()
    print ll.search(3)
    print ll.search(4)
    ll.remove(1)
    print "length:",ll.length()
    ll.travel()