做网站友情链接的步骤,湖南个人网络营销订制,gonzo wordpress,随州网站推广哪家专业一、前言
今天我们学习另一种非常重要的线性数据结构–链表#xff0c;之前我们已经学习了三种线性数据结构#xff0c;分别是动态数组#xff0c;栈和队列。其中队列我们额外学习了队列的另一种实现方式–循环队列。其实我们自己实现过前三个数据结构就知道#xff0c;它…一、前言
今天我们学习另一种非常重要的线性数据结构–链表之前我们已经学习了三种线性数据结构分别是动态数组栈和队列。其中队列我们额外学习了队列的另一种实现方式–循环队列。其实我们自己实现过前三个数据结构就知道它们底层均依托静态数组靠resize解决固定容量问题。而链表和前三种均不同它是真正的动态数据结构。 学好链表有利于
链表是最简单的动态数据结构方便你学习后面的二分搜索树Trie,AVL,红黑树等等更深入的理解引用或者指针更深入的理解递归辅助生成其他数据结构例如我们之前学习的栈队列可以通过链表实现亦或是其他复杂的数据结构如图哈希表等
二、链表
数据存储在节点Node中
class NodeT{T t; //数据Node next; //指向当前节点的下一个节点
}就像火车一样每一个节点就像一个个车厢车厢除了人(数据)还要和其他车厢进行连接以使得数据是整合在一起的用户可以方便的在所有的数据上进行查询等其他操作。而数据和数据之间的连接就是靠Node next决定的。 而我们的链表自然也不可能是无穷无尽的我们链表存储的数据一定是有限的那么最后一个节点它的next存储的就是一个NULL我们也可以反过来得知如果一个节点的NEXT是NULL那么就说明这个节点一定是最后一个节点。
优点真正的动态不需要处理固定容量的问题需要多少数据就生成多少节点并将它们连接起来。不需要像静态数组一样事先预定好一块儿固定空间。缺点丧失了随机访问的能力说白了就是不能像数组一样直接拿一个索引找出索引对应的元素。这是因为从底层机制上数组所开辟的空间在内存里是连续分布的所以我们可以直接去寻找索引对应的偏移直接计算机相应的数据所存储的地址直接用O(1)的复杂度就把这个元素找出来。但是链表不同链表是靠next一层一层连接的所以在计算机的底层每一个节点在内存的位置是不同的我们必须靠next一点一点的找到我们想要的元素这就是链表最大的缺点。
基于上述理论我们可以有如下数组和链表的对比
数组
数组最好用于索引有语意的情况。如scores[2]最大的优点支持快速查询
链表
链表不适合用于索引有语意的情况最大的优点动态
但是其实我们后续实现动态数组有说过我们处理的都是索引没有语意的情况对于这类不方便使用索引的数据我们使用链表存储这些数据是更合适的。由于它最大的优点就是动态。 我们可以先初步搭建一下我们链表的类首先创建一个链表类然后创建一个内部私有类Node节点就和我们之前提的是一样的
public class LinkedListT {//只有在链表结构内才能访问Node,链表结构外用户无法访问因为对于用户而言他们不需要指定链表的底层实现private class Node {public T data;public Node next;public Node(T data, Node next) {this.data data;this.next next;}public Node(T data) {this(data, null);}public Node() {this(null, null);}Overridepublic String toString() {return Node{ data data , next next };}}
}三、向链表添加元素
对于链表来说我们要想访问链表中的所有节点相应的必须把链表头存储起来通常呢链表的头结点叫作head,所以我们的LinkedList类中应该有一个Node类型的变量叫作head。它指向链表中的第一个节点。我们首先把我们linkedList的基础变量声明出来。
private Node head;private int size;public LinkedList() {this.head null;this.size 0;}public int getSize(){return size;}public boolean isEmpty(){return size 0;}
①往链表头部增加元素 我们之前学习数组添加元素的时候第一个说的方法是往数组末尾添加元素这是因为对于数组而言往数组末尾添加元素是比较方便的。 但链表则正好相反对于链表而言往连边头部增加元素是非常方便的。 这其实很好理解因为数组有size这个变量它直接指向的是第一个未被添加元素的位置所以直接往尾部添加很方便因为有size这个变量在跟踪数组的尾巴。 而链表我们有头部的变量但是我们没有相应的变量去跟踪链表的尾巴所以我们往链表头添加元素很方便。 例如我现在要插入一个666的节点图示如下
往链表头添加元素后我们要把这个元素和链表连接起来所以我们需要让新添加的Node指向我们的head,然后由于连起来后这个链表已经成了新的头节点所以我们要把新添加的Node赋值给我们的头结点。
node.next head;
head node;那么我们往头部插入元素实现就很简单
public void addFirst(T t){//声明一个新的节点将这个新节点指向我们的头结点然后再让新的节点成为头结点Node node new Node(t);node.next head;head node;size ;}其实上面的方法我们还有更优雅的写法 public void addFirst(T t){//声明一个新的节点将这个新节点指向我们的头结点然后再让新的节点成为头结点
// Node node new Node(t);
// node.next head;
// head node;//这一行代码干了上面三行代码的事head new Node(t,head);size ;}②往链表中间插入元素注这个操作不是常用操作练习用 例如往“索引”为2的位置插入元素 注意这里索引打了引号因为链表其实不存在索引这个概念如下图其实就相当于在1这个元素后面插入一个666的元素 那么我们的思路就是想要插入这个666的元素需要找到插入的位置的前一个节点的位置让这个节点的next指向我要插入的新节点然后新节点的next指向原来的前一个节点的next的节点。所以我们为了方便找到前一个节点的位置我们定义一个prev变量初始情况prev和head指向同一个位置而后面通过将prev移动找到对应的插入的位置的前一个节点的位置 所以我们的任务就是找到插入666之前的那个节点是谁。比如我们现在要插入的位置是“索引”为2所以插入之前的“索引”为1所以我们遍历一下prev指向“索引”为1的位置然后新的节点的next指向我们的原来“索引”为1的next即“索引”为2的节点然后将原来“索引”为1的next指向我们新的节点
node.next prev.next;
prev.next node;关键就是找到要添加的节点的前一个节点 有些人可能会注意到当我要把元素添加到索引为0的位置的时候此时索引为0的位置是没有前一个元素的我们需要特殊处理一下。 然后就是对于链表很重要的一点顺序 如果我把上述操作倒过来
prev.next node;
node.next prev.next;那么就会出现Node的next指向Node自己的错误所以顺序一定要注意。可以通过纸笔或者debug调试一下。那么我们的实现如下
//在链表的Index(0-based)位置添加新的元素epublic void add(T t, int index) {if (index 0 || index size) {throw new IllegalArgumentException(add element error:index should 0 index size);}//如果Index 0,由于索引为0的位置没有前一个元素所以我们直接特殊处理其实就相当于往头部添加元素if(index 0){addFirst(t);}else {Node prev head;for(int i 0;i index - 1;i ){prev prev.next;}Node node new Node(t);node.next prev.next;prev.next node;size ;}}那么add完成了后我们就可以很简单的完成再添加一个add方法了就是向链表末尾添加一个元素addLast(),其实就是add方法的index传size即可
public void addLast(T t){add(t,size);}那么以上就是链表的添加元素方法但其实我们的add()仍然不够优雅关键在于我们需要对Index0的处理方法特殊处理其实有一种方法可以直接让我们拜托这种特殊处理就是设立虚拟head结点这个我们后面会讲到
四、为链表设立虚拟头结点
我们之前说add方法的时候有一个不太优雅的地方就是当Index0的时候我们需要特殊处理原因就是头结点没有上一个节点那么解决思路也很简单我们就造一个虚拟的链表头结点它其实不存储任何的元素我们将这个NULL节点称之为我们链表的head,也叫做dummyHead即虚拟头结点。它其实就是索引为0对应的元素的前一个位置。那么这样添加当index 0时就不需要特殊处理了。 且我们现在prev是从dummyHead开始即索引为0对应的元素的前一个位置开始那么我们其实我们不再需要遍历Index-1次而直接遍历Index次就可以找到插入位置的前一个位置了说白了就是我的起点往前挪了一个位置那么我遍历次数自然就需要少1次 代码如下
//在链表的Index(0-based)位置添加新的元素epublic void add(T t, int index) {if (index 0 || index size) {throw new IllegalArgumentException(add element error:index should 0 index size);}Node prev dummyHead;for (int i 0; i index; i) {prev prev.next;}Node node new Node(t);node.next prev.next;prev.next node;size;}那么反过来我们的addFirst也可以通过add简化了 public void addFirst(T t) {//声明一个新的节点将这个新节点指向我们的头结点然后再让新的节点成为头结点add(t, 0);}
