链表(Linked List)是一种线性数据结构,它由一系列节点(Node)组成,每个节点包含两部分:数据和指向下(上)一个节点的引用(或指针)。链表中的节点按照线性顺序连接在一起(相邻节点不需要存储在连续内存位置),不像数组一样存储在连续的内存位置。链表通常由头节点(Head)来表示整个链表,而尾节点的下一个节点指向null,表示链表的结束。
链表有几种常见的类型,其中最常见的包括单链表、双链表。
// Java LinkedList 中Node的结构
class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
链表基本结构是节点,节点一般包含数据和指向节点的指针;节点只有指向下一个节点指针的叫单链表(Singly Linked List),有指向上一个节点的指针的叫双链表(Doubly Linked List)。
链表的一些关键特点:
链表的性质:
链表最基本的一些算法应用 是 根据要求操作节点指针 next 指针。
给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
在解决一些算法问题,同样可以定义多个指针指向多个链表节点(Node)来进行操作来完成解答。
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
本篇主要介绍了链表基本结构,以及相关一些算法问题分析。链表还可以结合其他数据结构、算法思想比如 哈希(Hash)、优先队列(Priority Queue)等解决一些算法问题;考虑到本系列文章希望能够承前启后,不至于出现一些先前文章未介绍到的数据结构与算法,因此后续文章中再代入分析。
另外,从出题人的角度分析算法的问题也是一个不错的选择,可能会带来不一样的总结与经验。
欢迎点个小红心,关注公众号 Java研究者 联系、交流~
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。