星星博客 »  > 

【数据结构】链表

在这里插入图片描述
线性结构:有且只有一个根节点,且每个节点最多有一个直接前驱和一个直接后继的非空数据结构

非线性结构:不满足线性结构的数据结构

链表的定义

链表是一种线性表数据结构;
从底层存储结构上看,链表不需要一整块连续的存储空间,而是通过“指针”将一组零散的内存块串联起来使用;
链表中的每个内存块被称为链表的“结点”,每个结点除了要存储数据外,还需要记录上(下)一个结点的地址。

1、链表一般分为:

单向链表

双向链表

环形链表

2、基本概念

链表实际上是线性表的链式存储结构,与数组不同的是,它是用一组任意的存储单元来存储线性表中的数据,存储单元不一定是连续的,

且链表的长度不是固定的,链表数据的这一特点使其可以非常的方便地实现节点的插入和删除操作

链表的每个元素称为一个节点,每个节点都可以存储在内存中的不同的位置,为了表示每个元素与后继元素的逻辑关系,以便构成“一个节点链着一个节点”的链式存储结构,

除了存储元素本身的信息外,还要存储其直接后继信息,因此,每个节点都包含两个部分,第一部分称为链表的数据区域,用于存储元素本身的数据信息,这里用data表示,

它不局限于一个成员数据,也可是多个成员数据,第二部分是一个结构体指针,称为链表的指针域,用于存储其直接后继的节点信息,这里用next表示,

next的值实际上就是下一个节点的地址,当前节点为末节点时,next的值设为空指针

python中链表的定义方式

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        l1 = ListNode() # 定义一个链表,注意定义的方式 ListNode()
        l1 = head
        return l1

在这里插入图片描述

3、链表特点

插入、删除数据效率高,只需要考虑相邻结点的指针改变,不需要搬移数据,时间复杂度是 O(1)。

随机查找效率低,需要根据指针一个结点一个结点的遍历查找,时间复杂度为O(n)。

与内存相比,链表的空间消耗大,因为每个结点除了要存储数据本身,还要储存上(下)结点的地址。

链表插入元素

在一个如下的链表中,index为2的地方,插入节点15。步骤如下:
第一步,先找到index为1的node节点23;
第二步,然后把节点15的next指针指向节点10;

image.png

第三步,把节点23的next指针指向15;

在这里插入图片描述

注意点:这里需要先把15节点的next指向10,然后再把23节点的next指向15,顺序不能打乱,要不然就找不到23节点后面的链表啦。

206.反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

# 双指针算法
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 定义两个变量,分别为空链表和链表head
        pre = None
        cur = head
        # 进行循环遍历,双指针
        while(cur):
            # sef.next是指向下一个节点的索引
            # 先把cur.next指向的值赋给temp
            temp = cur.next
            # 再把cur.next指向pre
            cur.next = pre
            # 在分别把pre和cur向前移动一位
            pre = cur
            cur = temp
        return pre

JAVA语言

借助外部空间的解法

由于题目并没有要求必须原地反转,因此可以借助外部空间实现。这里可以将单链表储存为数组,然后按照数组的索引逆序进行反转。但是,此方式比较浪费空间,而且需要两次遍历,效率不占优势。

public static Node ReverseList1(Node head)
    {
        if(head == null)
        {
            return null;
        }

        List<Node> nodeList = new List<Node>();
        while (head != null)
        {
            nodeList.Add(head);
            head = head.Next;
        }

        int startIndex = nodeList.Count - 1;
        for (int i = startIndex; i >= 0; i--)
        {
            Node node = nodeList[i];
            if (i == 0)
            {
                node.Next = null;
            }
            else
            {
                node.Next = nodeList[i - 1];
            }
        }
        // 现在头结点是原来的尾节点
        head = nodeList[startIndex];
        return head;
    }

相关文章