无头单向非循环java版的模拟实现
【本节目标】
1.ArrayList的缺陷
2.链表
1. ArrayList的缺陷
上节课已经熟悉了 ArrayList 的使用，并且进行了简单模拟实现。通过源码知道， ArrayList 底层使用数组来存储元素：
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{// ...
// 默认容量是10private static final int DEFAULT_CAPACITY = 10;//...
// 数组：用来存储元素transient Object[] elementData; // non-private to simplify nested class access// 有效元素个数private int size;public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}
// ...
} 由于其底层是一段连续空间，当 在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后 搬移，时间复杂度为 O(n) ，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景 。因此： java集合中又引入了LinkedList ，即链表结构。
2. 链表
2.1 链表的概念及结构
链表是一种 物理存储结构上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们重点掌握两种 :
头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2.2 无头单向非循环链表的实现
接口：
public interface Ilinklist {// 1、无头单向非循环链表实现//头插法void addFirst(int val);//尾插法void addLast(int val);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int val);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();//清空单链表void clear();//展示单链表void display();}
要有链表首先得有节点
如下就是使用内部类创建了个头结点
有数值和next节点的地址
在创建一个成员变量head，指向头结点。未初始化默认为null
我们可以写链表的插入
链表的头插不需要考虑是否为空的情况
链表的尾差需要考虑为空的情况，如果是空就直接返回，不进行插入
while(cur.next!=null)
这个循环是遍历到最后一个链表，再将它的next改为新节点的地址即可
随机位置插入
1.考虑给的位置是否合法
2.给的是0或者给的链表长度
3.在范围内的值找到index前一个的链表
4.进行连接
1.合法性
写了一个异常类
写了一个函数捕捉这个异常
再用try-catch来处理异常
2.给的是0或者给的链表长度
如果给的是0就进行头插
如果给的是链表长度就进行尾差
剩下的就比较简单
用了一个函数进行寻找index的前一个位置
再进行连接
链表的打印
再测试下插入是否满足要求
可见插入是满足需求的
是否包含某个元素
删除第一个数值为val的节点
测试
删除所有为为val的节点
测试
确实没有1出现，可见全部删除
删除所有存在val值的节点还有一个方法，创建一个哨兵位
测试
也是可以的
2.3总代码
接口
public interface Ilinklist {// 1、无头单向非循环链表实现//头插法void addFirst(int val);//尾插法void addLast(int val);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int val);//查找是否包含关键字key是否在单链表当中boolean contains(int val);//删除第一次出现关键字为key的节点void remove(int val);//删除所有值为key的节点void removeAllKey(int val);//得到单链表的长度int getSize();void clear();void display();}
indexNotLegalException.java
public class indexNotLegalException extends RuntimeException{public indexNotLegalException(){}public indexNotLegalException(String msg){super(msg);}
}
LinkList.java
public class LinkList implements Ilinklist {static class ListNode{public int val;ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;@Overridepublic void addFirst(int val) {//链表的头插ListNode node=new ListNode(val);node.next=head;head=node;}public void addLast(int val){//链表的尾差ListNode node=new ListNode(val);if(head==null){head=node;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=node;}public int getSize(){//获取链表的长度ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}public void addIndex(int index,int val){//1.判断合法性try{cheakIndexofAddIndex(index);}catch(indexNotLegalException e){e.printStackTrace();return;}//2.index==0||index==size()if(index==0){addFirst(val);return;}if(index==getSize()){addLast(val);return;}//3.找到index的前一个位置ListNode cur=findIndexSubOne(index);//4.进行连接ListNode node=new ListNode(val);node.next=cur.next;cur.next=node;}@Overridepublic boolean contains(int val) {ListNode cur=head;while(cur!=null){if(cur.val==val){return true;}cur=cur.next;}return false;}@Overridepublic void remove(int val) { //删除第一个节点为val的值if(head==null){return;}ListNode cur=head;if(cur.val==val){head=head.next;return;}while(cur.next!=null){if(cur.next.val==val){cur.next=cur.next.next;return;}cur=cur.next;}}@Overridepublic void removeAllKey(int val) {//删除链表所有值为val的节点/* if(head==null){return;}ListNode prev=head;ListNode cur=head.next;while(cur!=null){if(cur.val==val){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}if(head.val==val){head=head.next;}*/ListNode Head=new ListNode(0);Head.next=head;ListNode temp=Head;while(temp.next!=null){if(temp.next.val==val){temp.next=temp.next.next;}else{temp=temp.next;}}head=Head.next;}@Overridepublic void clear() {}@Overridepublic void display() {ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}private void cheakIndexofAddIndex(int index) throws indexNotLegalException{//判断指定位置插入的index是否合法if(index<0||index>getSize()){throw new indexNotLegalException("AddIndex的index不合法");}}private ListNode findIndexSubOne(int index){ListNode cur=head;while(index-1>0){cur=cur.next;index--;}return cur;}}test.java
public class test {public static void main(String[] args) {LinkList linkList=new LinkList();linkList.addFirst(1);linkList.addFirst(1);linkList.addFirst(1);linkList.addFirst(1);//上面是链表的头插linkList.display();System.out.println("==============");linkList.removeAllKey(1);//删除所有拥有1的节点linkList.display();}
}