数据结构和算法-6-链表和单链表的实现过程

一时失言乱红尘 2022-01-15 20:03 171阅读 0赞

这篇来学习单链表的结构和代码实现过程，重点要理解节点Node这个class的含义，一个节点包含两部分组成，数据和存储下一个节点的内存地址。

1.链表的定义

链表的定义  
链表（linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

![20190613153814492.png][]

上图就是一个单链表的表示。

2.单链表

单向链表也就是单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域（指针域），这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

![20190613160410337.png][]

*  表元素域elem用来存放具体的数据。
 *  链接域next用来存放下一个节点的位置。
 *  变量p指向链表的头节点的位置，从p出发能找到表中任意节点。

节点类实现

包下创建一个single\_link\_list.py模块。

# coding:utf-8
    
    
    class Node(object):
        """单链表的节点"""
        def __init__(self, item):
            """item存放数据元素"""
            self.item = item
            self.next = None

接下来需要定义单链表需要实现方法

is_empty() 链表是否为空
    length() 链表长度
    travel() 遍历整个链表
    add(item) 链表头部添加元素
    append(item) 链表尾部添加元素
    insert(pos, item) 指定位置添加元素
    remove(item) 删除节点
    search(item) 查找节点是否存在

我们先来实现链表的尾部添加元素，和判断是否为空，以及遍历和链表长度这四个方法。

运行后输出

True
    3
    =====遍历链表元素=====
    3
    5
    8

再来看看如何从头部添加元素，以及插入元素的实现代码

# coding:utf-8
    
    
    class Node(object):
        """节点"""
        def __init__(self, item):
            self.item = item
            self.next = None
    
    
    class SingleLinkList(object):
        """单链表"""
    
        def __init__(self, node = None):
            self.__head = node
    
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head == None
    
        def length(self):
            """链表长度"""
            # cur游标 用来移动遍历元素
            cur = self.__head
            # count记录数量
            count = 0
            while cur != None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历整个链表"""
            cur = self.__head
            while cur != None:
                print(cur.item, end=" ")
                cur = cur.next
    
        def add(self, item):
            """链表头部添加元素"""
            node = Node(item)
            node.next = self.__head
            self.__head = 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
    
        def insert(self, pos, item):
            """指定位置插入元素"""
            # 如果要插入位置小于等于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
                # 当循环退出，pre指向pos-1位置
                node = Node(item)
                node.next = pre.next
                pre.next = node
    
        def remove(self, item):
            """删除节点"""
            pass
    
    
    if __name__ == "__main__":
        list = SingleLinkList()
    
        print(list.is_empty())
        list.append(3)
        list.append(5)
        list.append(8)
        print(list.length())
        print("=====遍历链表元素=====")
        list.travel()
        print("从头部添加元素")
        list.add(13)
        list.insert(2, 45)
        print("插入后元素为")
        list.travel()

运行效果

True
    3
    =====遍历链表元素=====
    3 5 8 从头部添加元素
    插入后元素为
    13 3 45 5 8

最后来看看删除元素和查找元素的代码

# coding:utf-8
    
    
    class Node(object):
        """节点"""
        def __init__(self, item):
            self.item = item
            self.next = None
    
    
    class SingleLinkList(object):
        """单链表"""
    
        def __init__(self, node = None):
            self.__head = node
    
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head == None
    
        def length(self):
            """链表长度"""
            # cur游标 用来移动遍历元素
            cur = self.__head
            # count记录数量
            count = 0
            while cur != None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历整个链表"""
            cur = self.__head
            while cur != None:
                print(cur.item, end=" ")
                cur = cur.next
    
        def add(self, item):
            """链表头部添加元素"""
            node = Node(item)
            node.next = self.__head
            self.__head = 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
    
        def insert(self, pos, item):
            """指定位置插入元素"""
            # 如果要插入位置小于等于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
                # 当循环退出，pre指向pos-1位置
                node = Node(item)
                node.next = pre.next
                pre.next = node
    
        def search(self, item):
            """查找元素是否存在"""
            cur = self.__head
            while cur != None:
                if cur.item == item:
                    return True
                else:
                    cur = cur.next
            return False
    
        def remove(self, item):
            """删除节点"""
            cur = self.__head
            pre = None
            while cur != None:
                if cur.item == item:
                    if cur == self.__head:
                        self.__head = cur.next
                    else:
                        pre.next = cur.next
                    break
                else:
                    pre = cur
                    cur = cur.next
    
    
    if __name__ == "__main__":
        list = SingleLinkList()
        list.append(3)
        list.append(5)
        list.append(8)
        list.travel()
        print("\r")
        print("查找元素5在不在")
        print(list.search(5))
        list.remove(5)
        list.travel()

运行下上面测试

3 5 8 
    查找元素5在不在
    True
    3 8

[20190613153814492.png]: /images/20220115/7414314741b5427f8d0c68839a143a2a.png
[20190613160410337.png]: /images/20220115/45fb3a0a5cc0459290fcc552f9378380.png