无头单向非循环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();}
}