网站建设规划方案书,网站开发项目可行性,wordpress 注册 中文版,知了seo【本节目标】
1.ArrayList的缺陷
2.链表 1. ArrayList的缺陷 上节课已经熟悉了 ArrayList 的使用#xff0c;并且进行了简单模拟实现。通过源码知道#xff0c; ArrayList 底层使用数组来存储元素#xff1a; public class ArrayListE extends AbstractList…【本节目标】
1.ArrayList的缺陷
2.链表 1. ArrayList的缺陷 上节课已经熟悉了 ArrayList 的使用并且进行了简单模拟实现。通过源码知道 ArrayList 底层使用数组来存储元素 public class ArrayListE extends AbstractListEimplements ListE, 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 nodenew ListNode(val);node.nexthead;headnode;}public void addLast(int val){//链表的尾差ListNode nodenew ListNode(val);if(headnull){headnode;return;}ListNode curhead;while(cur.next!null){curcur.next;}cur.nextnode;}public int getSize(){//获取链表的长度ListNode curhead;int count0;while(cur!null){count;curcur.next;}return count;}public void addIndex(int index,int val){//1.判断合法性try{cheakIndexofAddIndex(index);}catch(indexNotLegalException e){e.printStackTrace();return;}//2.index0||indexsize()if(index0){addFirst(val);return;}if(indexgetSize()){addLast(val);return;}//3.找到index的前一个位置ListNode curfindIndexSubOne(index);//4.进行连接ListNode nodenew ListNode(val);node.nextcur.next;cur.nextnode;}Overridepublic boolean contains(int val) {ListNode curhead;while(cur!null){if(cur.valval){return true;}curcur.next;}return false;}Overridepublic void remove(int val) { //删除第一个节点为val的值if(headnull){return;}ListNode curhead;if(cur.valval){headhead.next;return;}while(cur.next!null){if(cur.next.valval){cur.nextcur.next.next;return;}curcur.next;}}Overridepublic void removeAllKey(int val) {//删除链表所有值为val的节点/* if(headnull){return;}ListNode prevhead;ListNode curhead.next;while(cur!null){if(cur.valval){prev.nextcur.next;curcur.next;}else{prevcur;curcur.next;}}if(head.valval){headhead.next;}*/ListNode Headnew ListNode(0);Head.nexthead;ListNode tempHead;while(temp.next!null){if(temp.next.valval){temp.nexttemp.next.next;}else{temptemp.next;}}headHead.next;}Overridepublic void clear() {}Overridepublic void display() {ListNode curhead;while(cur!null){System.out.print(cur.val );curcur.next;}System.out.println();}private void cheakIndexofAddIndex(int index) throws indexNotLegalException{//判断指定位置插入的index是否合法if(index0||indexgetSize()){throw new indexNotLegalException(AddIndex的index不合法);}}private ListNode findIndexSubOne(int index){ListNode curhead;while(index-10){curcur.next;index--;}return cur;}} test.java public class test {public static void main(String[] args) {LinkList linkListnew LinkList();linkList.addFirst(1);linkList.addFirst(1);linkList.addFirst(1);linkList.addFirst(1);//上面是链表的头插linkList.display();System.out.println();linkList.removeAllKey(1);//删除所有拥有1的节点linkList.display();}
}
