LinkedList和链表(上)

1. 顺序表ArrayList的缺点和优点

优点:

1> 在给定下标进行查找的时候,时间复杂度是O(1)

缺点:

1> 插入数据必须移动其他数据,最坏情况下,插入到0位置,时间复杂度为O(N)

2> 删除数据也需要移动数据,最坏情况下,就是删除0位置.时间复杂度为O(N)

3> 扩容之后(1.5倍扩容)假设我们只用了扩容部分的一点点,这个就造成了空间的浪费

总结: 顺序表比较适合进行给指定下标查找的情景

由此我们引出了链表来解决这三个问题.

2. 链表的概念以及结构

2.1 链表的结构

链表是一种逻辑上顺序存储,物理上不一定连续存储的结构.它由若干个结点通过引用链接组成,每个结点分为value数据域和next引用域组成.

2.2 链表的类型

根据链表是否能够直接访问上一个结点,我们分为:单向和双向链表

根据链表有没有头节点我们分为:带头和不带头

根据链表是否首尾相连我们分为:循环和非循环

根据排列组合,我们可以了解到由8种组合:单向带头循环,单向带头不循环,单向不带头循环,单向不带头不循环,双向带头循环,双向带头不循环,双向不带头循环,双向不带头不循环.我们最主要学习的是单向不带头非循环,双向不带头循环

我们来看几个图简单了解一下

单向不带头非循环链表: 结构简单一般不会用来单独存储数据.实际过程种事作为其他数据结构的字结构,比如哈希桶,图的邻接表等等.

双向不带头非循环链表:

双向不带头循环链表: 底层的LinkedList就是这么实现的

3. 链表的实现

3.1 前置变量和类的解释

我们为了更好的了解底层代码,我们来自己实现一个链表

我们先写一个Ilist接口

然后我们再为链表写出一个类:MySingleList,实现Ilist接口,并且重写里面的方法

结点,作为我们链表里面的一个整体,我们用内部类来表示,叫做:ListNode.每一个结点里面存在数据域(val,存链表的数据)和next域(存结点的地址)这里我们实现的是单向带头不循环的链表,因此next指向的是下一个结点,保存的是下一个结点的地址.并且我们提供一个构造方法,每次创建结点都要把数据域的值传进去.

这个地方我要强调一下,就是我们引用类型我们创建出来的实例,如果没有重写toString方法里面存放的就是地址

如果重写了里面的方法,就根据方法来执行

然后我们创建一个引用类型变量,不重写里面的toString方法,这个变量里面存的也是地址

package LinkedList和链表;
class Student {public int id;
}
class Person {public int age;public String name;public Student s1;@Overridepublic String toString() {return "Person{" +"age=" + age +", name='" + name + '\'' +'}';}
}
public class t3 {public static void main(String[] args) {Person p = new Person();Student s1 = new Student();p.s1 = s1;System.out.println(p.s1);System.out.println(p);}
}
//
LinkedList和链表.Student@1540e19d
Person{age=0, name='null'}Process finished with exit code 0

head的头节点我们要单独定义出来,因为head不是结点内部类里面的成员,它是独立于其他节点的,其他节点都是要在head节点存在的基础上再进行创建和连接.

我们先通过穷举的方式来理解节点这个内部类,我们写了一个createList()方法,手动来连接节点成一个链表.我们先把节点内部类进行实例化,并且传进去相关的值.我们再把每个节点的next域保存指向下一个节点,listNode1.next = listNode2;就表示,我调用listNode1的next属性,把listNode2的地址传给它

我们在main里面进行测试,发现确实是把节点连成了一个链表

3.2 具体的重写方法的介绍

3.2.1 遍历链表 display()

我们通过display()方法来遍历链表,打印链表中的每一个元素

1> 怎么从一个节点走到下一个节点? 先取出值然后 cur = cur.next(我们为了知道头节点的位置,我们选择用cur来代替head来进行遍历)

2> 怎么判断所有节点都遍历完: cur.next == null

3.2.2 求链表的结点个数 size()

定义一个变量count;我们遍历每一个结点,并且count++.

这里注意一下,我们的判断条件,

这个图表示了cur != null的情况

这个图表示了 cur.next != null的情况

由此我们可以看出,如果想遍历并且打印每一个元素,我们应该使用cur !=null作为判断条件

3.2.3 链表中是否包含某个元素 contains()

我们使用contains()方法来判断这个元素是否在链表中,我们需要遍历整个链表,并且每一次遍历需要对cur当前所指向的结点val进行和key的比较,如果存在就返回true,如果经过了遍历之后还没有找到,则会返回false.

1. 实例化一个结点. 2. 改变插入节点的next 3. 改变head

3.2.4 头插法addFirst()

头插法: 如果链表不为null,就先创建一个结点,再连接head的结点,最后让head指向新的结点

其中 node.next = this.head; this.head = node;这俩行代码是不能换位置的,如果我们head直接指向head,node后面就没有结点了.

1. 实例化一个结点 2. 找到最后一个cur 3. cur.next = node;

3.2.5 尾插法addLast()

尾插法: 我们把待插入的结点放在链表的最后一个位置,同样也要考虑head为null的情况

在这里做一个小总结:

如果我们想让cur停在最后一个节点的位置 cur.next != null;

如果我们想把整个链表的每一个节点都遍历完,那么cur != null

头插法的时间复杂度为O(1)

尾插法的时间复杂度为O(N)

3.2.6 在任意位置插入元素addIndex()

先判断是不是在首位插入,如果是的话就调用上述的相应方法,如果不是,那么就是中间的位置

我们就需要先找到index的前一个,我们调用searchPre方法

1. 让cur 走 index- 1步,找到要插入的前一个位置

然后为你产生一个新的节点,把数据传进去然后这么操作

2. node.next = cur.next; cur.next = node;

这里面我们要注意,因为我们是通过下标来进行插入的,因此,我们需要对下标的合法性进行判断

3.2.7 删除元素remove()

我们对一个元素进行删除,首先要看这个链表是不是空的,然后我们要判断并这个元素是否存在,并且要获得它的前一个元素.然后进行下标的操作即可

这个是找到前一个元素的方法findPre()

3.2.8 删除所有值为key的元素removeAllKey()

在删除这个元素之前,我们需要判断这个链表是不是空的也就是头节点为null,然后我们进行遍历,每次到一个节点就判断它的val和我们要删除的key是不是相同,如果相同,我们就让删除的节点的前一个结点直接指向删除的后一个结点.然后更新cur结点.但是在这个过程中,我们有个问题,就是head结点并没有判断,因为我们的cur是从当前结点的下一个结点开始的.

3.2.9 清空链表中的所有元素clear()

也就是我们需要把链表所有的结点都置为空(如果是引用数据类中,数据域也要置为空)

这里要注意,最后我们的cur,curNext都会置空,但是我们的head一直没有置空,因此我们要手动把head也置空.

3.3 整体代码

package LinkedList和链表;import java.util.List;public class MySingleList implements Ilist{//TODO 先构造一个链表结构//我们把一个个结点构造成内部类static class ListNode {public int val;public ListNode next;//这里面存的是结点的地址public ListNode(int val) {this.val = val;}}//TODO head头节点//head是属于链表的成员,而不是结点内部类的成员,所以要定义在外面public ListNode head;
//    public int usedSize;//有效数据元素的数量//先通过穷举的方法来理解这个结构public void createList() {ListNode listNode1 = new ListNode(1);//每引用类型的变量名存着它这个引用类型变量的地址ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;listNode5.next = null;this.head = listNode1;}//TODO 1.遍历列表,打印链表的每一个元素//怎么从一个结点走到下一个结点: 先取出值 再head = head.next//怎么判断所有结点都遍历完: head.next == null ??这样会漏掉最后一个结点,因此head == null才是终止条件@Overridepublic void display() {ListNode cur = this.head;//为了防止我们遍历一遍链表我们头结点的地址就找不到了while (cur != null) {//是否遍历完了链表System.out.print(cur.val + " ");cur = cur.next;//如何从当前位置结点指向下一个结点}System.out.println();}//TODO 2.求链表的结点个数//遍历每一个结点,count++@Overridepublic int size() {int count = 0;ListNode cur = this.head;while (cur != null) {count++;cur = cur.next;}return count;}//TODO 3.链表中是否包含某个元素@Overridepublic boolean contains(int key) {ListNode cur = this.head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//头插法: 如果链表不为null 先创建一个结点 再链接head的结点 最后让head指向新的结点//如果head为null 直接head指向新结点即可@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);if(this.head == null) {//其实也可以不要ifthis.head = node;} else {node.next = this.head;this.head = node;}}
//TODO 4.尾插法 把待插入的结点放在链表的最后一个位置//1. 实例化一个结点,2. 找到最后一个结点cur,3. cur.next = node;//head为空@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);ListNode cur = this.head;if (this.head == null) {this.head = node;} else {//找到尾巴while (cur.next != null) {//cur指向的是最后一个结点cur = cur.next;}//现在指向最后一个结点cur.next = node;}}//TODO 总结//如果向让cur停在最后一个结点的位置 cur.next != null//如果想把整个链表的每一个结点都遍历完,那么cur != null//头插法的时间复杂度O(1)//尾插法的时间复杂度O(N)//链表的插入只要改变指向即可//TODO 5.任意一个位置插入元素//我们需要找到index的前一个元素 node.next = cur.next,cur.next = node//1.让cur走index-1步//2. node.next = cur.next,cur.next = node 这里不能换过来//在插入一个结点的时候,一定要先绑定后面的这个结点@Overridepublic void addIndex(int index, int data) throws IndexIlleage{//判断index的合法性if(index < 0 || index > size()) {throw new IndexIlleage("下标非法! "+ index);}//如果是往第一个位置插,就调用头插法if (index == 0) {addFirst(data);return;}//如果是在最后一个位置插,就用尾插法if (index == size()) {addLast(data);return;}//如果是在中间插的话,我们就需要找到index的前一个ListNode cur = searchPre(index);ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}//找到index的前一个结点private ListNode searchPre(int index) {ListNode cur = this.head;int count = 0;while (count != index - 1) {cur = cur.next;count++;}return cur;}//TODO 6.删除元素// 1.找到删除元素的前一个cur.next.value == key@Overridepublic void remove(int key) {//如果为空,一个结点都没有,无法删除if(this.head == null) {System.out.println("链表为空,无法删除!");return;}//如果我们要删去的是第一个元素if(this.head.val == key){this.head = this.head.next;}//1.找到前驱ListNode preNode = findPre(key);//2.判断返回值是否为空if(preNode == null) {System.out.println("没有这个元素");return;}//3.删除元素(修改指向即可)ListNode delNode = preNode.next;preNode.next = delNode.next;//delNode是局部变量,当这个方法结束了,局部变量就没了}//找到前一个元素的位置private ListNode findPre(int key) {ListNode cur = this.head;while (cur.next != null) {//避免空指针异常,因为我们要用到下一个结点的valif(cur.next.val == key){return cur;}cur = cur.next;}return null;}
//TODO 7.删除所有值为key的元素@Overridepublic void removeAllKey(int key) {//判断头节点是不是空的if(this.head == null) {return;}//判断头结点是不keyif(head.val == key) {this.head = this.head.next;}ListNode prev = head;ListNode cur = head.next;//我们遍历除了head后面的元素while (cur != null) {if (cur.val == key) {prev.next = cur.next;cur = cur.next;} else {prev = cur;cur = cur.next;}}}//TODO 清空链表所有的元素//每一个结点数值域(可能为引用数据类型)@Overridepublic void clear() {
//    head = null;ListNode cur = head;while (cur != null) {ListNode curNext = cur.next;cur.next = null;//cur.val = null;如果是引用数据类型cur = curNext;}//后面所有的结点都置为null了,但是head还没有置为空head = null;}}package LinkedList和链表;public class Test {public static void main(String[] args) {MySingleList mySingleList = new MySingleList();mySingleList.createList();System.out.println("777");mySingleList.display();System.out.println(mySingleList.size());System.out.println(mySingleList.contains(1));//使用头插法来mySingleList.addFirst(12);mySingleList.addFirst(22);mySingleList.addFirst(32);mySingleList.addFirst(42);mySingleList.addLast(90);mySingleList.addLast(12);mySingleList.addLast(12);mySingleList.addLast(12);mySingleList.display();System.out.println(mySingleList.size());System.out.println(mySingleList.contains(1));mySingleList.addIndex(1,3);mySingleList.addIndex(0,3);mySingleList.addIndex(1,3);System.out.println(mySingleList.size());mySingleList.addIndex(9,78);mySingleList.display();mySingleList.remove(90);mySingleList.display();mySingleList.remove(78);mySingleList.display();mySingleList.removeAllKey(12);mySingleList.display();//        mySingleList.addIndex(10,90);}
}
package LinkedList和链表;public class IndexIlleage extends RuntimeException{public IndexIlleage(String s) {super(s);}
}package LinkedList和链表;public interface Ilist {//头插法void addFirst(int data);void addLast(int data);void addIndex(int index,int data);boolean contains(int key);public void remove(int key);//删除所有值为key的节点void removeAllKey(int key);int size();void clear();void display();
}