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;
@Override
public 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才是终止条件
@Override
public void display() {
ListNode cur = this.head;//为了防止我们遍历一遍链表我们头结点的地址就找不到了
while (cur != null) {//是否遍历完了链表
System.out.print(cur.val + " ");
cur = cur.next;//如何从当前位置结点指向下一个结点
}
System.out.println();
}
//TODO 2.求链表的结点个数
//遍历每一个结点,count++
@Override
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//TODO 3.链表中是否包含某个元素
@Override
public 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指向新结点即可
@Override
public void addFirst(int data) {
ListNode node = new ListNode(data);
if(this.head == null) {//其实也可以不要if
this.head = node;
} else {
node.next = this.head;
this.head = node;
}
}
//TODO 4.尾插法 把待插入的结点放在链表的最后一个位置
//1. 实例化一个结点,2. 找到最后一个结点cur,3. cur.next = node;
//head为空
@Override
public 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 这里不能换过来
//在插入一个结点的时候,一定要先绑定后面的这个结点
@Override
public 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
@Override
public 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) {//避免空指针异常,因为我们要用到下一个结点的val
if(cur.next.val == key){
return cur;
}
cur = cur.next;
}
return null;
}
//TODO 7.删除所有值为key的元素
@Override
public void removeAllKey(int key) {
//判断头节点是不是空的
if(this.head == null) {
return;
}
//判断头结点是不key
if(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 清空链表所有的元素
//每一个结点数值域(可能为引用数据类型)
@Override
public 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();
}
