网站找哪家做,seo网站设计就业前景,滨州网站建设滨州,内蒙古最新消息文章目录 1. ArrayList存在的问题2. 链表定义2.1 链表的概念及结构2.2 链表的组合类型 3. 链表的实现3.1 单向、不带头、非循环链表的实现3.2 双向、不带头节点、非循环链表的实现 4.LinkedList的使用4.1 什么是LinkedList4.2 LinkedList的使用4.2.1. LinkedList的构造4.2.2. L… 文章目录 1. ArrayList存在的问题2. 链表定义2.1 链表的概念及结构2.2 链表的组合类型 3. 链表的实现3.1 单向、不带头、非循环链表的实现3.2 双向、不带头节点、非循环链表的实现 4.LinkedList的使用4.1 什么是LinkedList4.2 LinkedList的使用4.2.1. LinkedList的构造4.2.2. LinkedList的其他常用方法介绍4.2.3. LinkedList的遍历 5. ArrayList和LinkedList的区别 1. ArrayList存在的问题
ArrayList底层使用连续的空间任意位置插入或删除元素时需要将该位置后序元素整体往前或者往后搬移故时间复杂度为O(N)增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。
由于其底层是一段连续空间当在ArrayList任意位置插入或者删除元素时就需要将后序元素整体往前或者往后搬移时间复杂度为O(n)效率比较低因此ArrayList不适合做任意位置插入和删除比较多的场景。因此java集合中又引入了LinkedList即链表结构。
2. 链表定义
2.1 链表的概念及结构
链表是一种常见的数据结构它由一系列节点组成每个节点包含两部分数据元素 (value) 和指向下一个节点的指针 ( next 域 )。通过这些节点的连接可以形成一个链式结构。 【单个节点】 节点Node链表的基本单元包含数据域和next指针域。数据域可以是任意类型的数据指针指向下一个节点。每个节点都是一个对象。 【节点组成的链式结构】
结论 链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
2.2 链表的组合类型
1、单向或者双向
根据节点的指针数量链表可以分为单向链表和双向链表。 单向链表每个节点只有一个指针指向下一个节点
双向链表每个节点有两个指针分别指向前一个节点和后一个节点。
2、带头或者不带头
带头节点的链表在第一个节点之前有一个额外的头节点用于标识链表的起始位置。head的value是无意义的如果想从最开头插入数据时head是不可变的从head后面插入
不带头节点的链表则直接以第一个节点作为链表的起始位置。head是第一个节点有value的如果想从最开头插入数据时head是可变的变成新插入的节点
3、是否循环 循环链表是在链表的尾部节点和头部节点之间形成一个循环连接使得链表的最后一个节点指向头部节点。 结合上述结构可以组合出8中链表种类 单向、带头节点、非循环链表 单向、带头节点、循环链表
单向、不带头节点、非循环链表重点 单向、不带头节点、循环链表
双向、不带头节点、非循环链表重点 双向、不带头节点、循环链表
双向、带头节点、非循环链表 双向、带头节点、循环链表
3. 链表的实现
3.1 单向、不带头、非循环链表的实现
节点的定义 //静态内部类定义节点public static class ListNode {public int data;//数据域public ListNode next;//指向下一个节点public ListNode(int data) {this.data data;}}public ListNode head; // 表示当前链表的头节点 方便找到链表的第一个元素2. 创建链表穷举法
public void createLinkedList() {ListNode node1 new ListNode(12);ListNode node2 new ListNode(23);ListNode node3 new ListNode(34);ListNode node4 new ListNode(45);ListNode node5 new ListNode(56);//把链表的节点连起来node1.next node2;node2.next node3;node3.next node4;node4.next node5;//使用head节点来记录链表的入口this.head node1;}使用debug发现所有节点链接起来了 之后可以使用head节点获取所有的节点
打印链表
1 怎么从一个节点走向下一个节点 移动head走向下一个节点使用head head.next;就可以实现 2怎么判断所有节点都遍历完 当head指向null时则所有节点遍历完毕 public void display() {ListNode cur this.head;//防止其他方法无法使用head无法找到链表的第一个元素使用临时变量curwhile (cur ! null) {//当cur指向null时则所有节点遍历完循环结束System.out.print(cur.value );cur cur.next;//不断移动cur指向下一个节点}System.out.println();}头插法添加数据
头插法插入数据分为三步 1实例化一个节点 2改变插入结点的next指向原来链表的第一个节点 3改变head指向新节点
Overridepublic void addFirst(int data) {ListNode listNode new ListNode(data);if (this.head null) {this.head listNode;} else {listNode.next this.head;this.head listNode;}}尾插法添加数据
尾插法添加数据分为二步 1实例化一个节点 2找到最后一个节点 3将链表的原来的最后一个节点指向新的节点
public void addLast(int data) {ListNode listNode new ListNode(data);if (this.head null) {this.head listNode;} else {ListNode cur this.head;while (cur.next ! null) {cur cur.next;}cur.next listNode;}}【小总结】 如果想让cur指向最后一个节点的位置使用cur.next null 如果想把整个链表遍历完成那么就是cur null 5.任意位置插入,第一个数据节点为0号下标
在链表随意位置插入数据分为四步 1找到该节点要插入位置的前一个节点cur前一个节点的原因可以由前一个节点得到后一个节点无法无法从后一个节点得到前一个结点),让cur走index-1步。 2实例化一个节点 3让新插入的节点的next指向要插入位置的节点,listNode.next cur.next; 4让要插入位置的前一个节点cur的next指向新节点,cur.next listNode; 注意3和4的顺序要正确再插入一个节点时一定要先绑定后面这个节点 public void addIndex(int index, int data) {if(index0||indexsize()){//要先判断index的合法性throw new IndexOutOfBounds(链表下标越界);//自定义异常链表下标越界}if(index 0){//在第一个位置插入使用头插法的方法addFirst(data);}else if(index size()){//在最后一个位置插入使用尾插法的方法addLast(data);}else {//在中间位置插入ListNode listNode new ListNode(data);//要插入的节点ListNode cur searchPrev(index);//要插入位置的前一个节点listNode.next cur.next;cur.next listNode;}}private ListNode searchPrev(int index){ListNode cur this.head;int count 0;while (count ! index -1){cur cur.next;count;}return cur;}
删除第一次出现关键字为key的节点 删除链表中的节点分为三步 1找到要删除节点的前一个节点cur 2 标记要删除的要素也可以不要这一步ListNode del cur.next 3让cur的next指向要删除的节点的下一个节点要删除的节点没有被引用JVM会自动回收 在第一步中找到要删除节点的前一个节点cur需要找到cur.next.value 和 key的值相等的节点如果是引用类型时现需要使用equals方法而不是 还有一种情况当要删除的数据是第一个节点时只需要让head指向第二个节点即可做到删除第一个节点 public void remove(int key) {//当要删除的数据是第一个节点if (this.head.value key) {this.head this.head.next;} else {//找到前驱ListNode cur getPrev(key);//判断前驱是否存在if (cur null) {System.out.println(要删除的数字不存在);} else {//删除节点ListNode del cur.next;cur.next del.next;}}}private ListNode getPrev(int key) {ListNode cur this.head;while (cur ! null) {if (cur.next.value key) {return cur;}cur cur.next;}return null;}删除所有值为key的节点
删除所有值为key的节点分为三步 1遍历链表找到要删除节点cur 2 让cur的上一个节点指向cur的下一个节点删除cur 3继续遍历链表找到所有与key相等的节点重复12步骤直至遍历完链表 还有要考虑一种情况当要删除的数据是第一个节点时只需要让head指向第二个节点即可做到删除第一个节点
public void removeAllKey(int key) {if(this.head null){return;}ListNode prev this.head;ListNode cur this.head.next;while (cur ! null) {if (cur.value key) {prev.next cur.next;cur cur.next;} else {prev cur;cur cur.next;}}if (this.head.value key) {this.head this.head.next;return;}}清空链表
清空链表分为两种方式 方式一直接将head置为null不推荐 方式二遍历节点将每个节点的数值域和next域置为空
public void clear() {ListNode cur this.head;while (cur ! null) {ListNode curNext cur.next;
// cur.value null;// 引用类型value要置为nullcur.next null;cur curNext;}this.head null;}完整代码 ILst接口
public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index, int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();public void clear();public void display();
}自定义异常IndexOutOfBounds类
public class IndexOutOfBounds extends RuntimeException{public IndexOutOfBounds(String message) {super(message);}
}MyLinkedList类
public class MyLinkedList implements IList {//静态内部类public static class ListNode {public int value;public ListNode next;public ListNode(int value) {this.value value;}}public ListNode head; //方便找到链表的第一个元素public void createLinkedList() {ListNode node1 new ListNode(12);ListNode node2 new ListNode(23);ListNode node3 new ListNode(34);ListNode node4 new ListNode(45);ListNode node5 new ListNode(56);//把表节点连起来node1.next node2;node2.next node3;node3.next node4;node4.next node5;//使用head节点来记录链表的入口this.head node1;}//头插法Overridepublic void addFirst(int data) {ListNode listNode new ListNode(data);if (this.head null) {this.head listNode;} else {listNode.next this.head;this.head listNode;}}//尾插法Overridepublic void addLast(int data) {ListNode listNode new ListNode(data);if (this.head null) {this.head listNode;} else {ListNode cur this.head;while (cur.next ! null) {cur cur.next;}cur.next listNode;}}Overridepublic void addIndex(int index, int data) {if (index 0 || index size()) {//要先判断index的合法性throw new IndexOutOfBounds(链表下标越界);//自定义异常链表下标越界}if (index 0) {//在第一个位置插入使用头插法的方法addFirst(data);} else if (index size()) {//在最后一个位置插入使用尾插法的方法addLast(data);} else {//在中间位置插入ListNode listNode new ListNode(data);//要插入的节点ListNode cur searchPrev(index);//要插入位置的前一个节点listNode.next cur.next;cur.next listNode;}}private ListNode searchPrev(int index) {ListNode cur this.head;int count 0;while (count ! index - 1) {cur cur.next;count;}return cur;}Overridepublic boolean contains(int key) {ListNode cur this.head;while (cur ! null) {if (cur.value key) {return true;}cur cur.next;}return false;}Overridepublic void remove(int key) {if (this.head.value key) {this.head this.head.next;} else {ListNode cur getPrev(key);if (cur null) {System.out.println(要删除的数字不存在);} else {ListNode del cur.next;cur.next del.next;}}}private ListNode getPrev(int key) {ListNode cur this.head;while (cur ! null) {if (cur.next.value key) {return cur;}cur cur.next;}return null;}Overridepublic void removeAllKey(int key) {if (this.head null) {return;}ListNode prev this.head;ListNode cur this.head.next;while (cur ! null) {if (cur.value key) {prev.next cur.next;cur cur.next;} else {prev cur;cur cur.next;}}if (this.head.value key) {this.head this.head.next;return;}}Overridepublic int size() {int count 0;ListNode cur this.head;while (cur ! null) {cur cur.next;count;}return count;}Overridepublic void clear() {ListNode cur this.head;while (cur ! null) {ListNode curNext cur.next;
// cur.value null;cur.next null;cur curNext;}this.head null;}Overridepublic void display() {ListNode cur this.head;while (cur ! null) {System.out.print(cur.value );cur cur.next;}System.out.println();}
}3.2 双向、不带头节点、非循环链表的实现
结点的定义 static class ListNode {public int val;//数值域public ListNode next;//指针域指向下一个节点public ListNode prev;//指针域指向前一个节点public ListNode(int val) {this.val val;}}2. 头插法 第一步让新插入的next 指向head节点 第二步让head节点的prev指向新插入的节点 第三步让head指向新插入的节点 public void addFirst(int data) {ListNode node new ListNode(data);if(head null){head node;last node;}else {node.next head;head.prev node;head node;}}尾插法 第一步让last节点的next指向新插入的节点 第二步让新插入的prev指向last节点 第三步让last指向新插入的节点 public void addLast(int data) {ListNode node new ListNode(data);if (head null) {head node;last node;} else {last.next node;node.prev last;last node;}}在指定位置插入元素 第一步判断要插入的位置是否合法0index链表的长度 第二步判断要插入的节点是否在0位置如果在0位置那么就使用头插法 第三步判断要插入的节点是否在最后一个位置如果在最后一个位置那么就使用尾插法 第四步如果要在中间插入需要插入位置前一个节点的next域指向新节点新节点的next域指向插入位置的原来的节点新节点的prev域指向需要插入位置前一个节点需要插入位置的原来的节点的prev域指向新节点改变四个指针域的指向便可以将新节点插入需要插入的位置。 public void addIndex(int index, int data) {int len size();//index小于0或者大于链表的长度插入位置不合法if (index 0 || index len) {throw new IndexOutOfBounds(要插入的位置小于0或者超过链表的长度该位置不合法);}//如果在第一个节点插入使用头插法if (index 0) {addFirst(data);return;}//如果在最后一个节点插入使用尾插法if (index len) {addLast(data);return;}//中间位置//获取要插入的位置的节点ListNode cur getNode(index);//新插入的节点ListNode node new ListNode(data);//在中间位置插入节点元素ListNode prev cur.prev;prev.next node;node.next cur;node.prev prev;cur.prev node;}public ListNode getNode(int index) {ListNode cur this.head;while (index ! 0) {index--;cur cur.next;}return cur;}5.删除指定节点 总共分为三种情况分别如下 特殊情况还需要考虑一种特殊情况当量表中只存在一个节点并且该结点时需要删除的节点的情况 public void remove(int key) {ListNode cur this.head;while (cur ! null) {//判断是否找到目标节点if(cur.val key) {//要删除的节点是头节点的情况if(cur head) {head head.next;//链表中只有头节点一个节点,删除之后链表为空链表last需要置为nullif(head null) {last null;}else {//链表中不止一个节点需要将头节点的prev置为nullhead.prev null;}return;}//要删除的节点是尾节点的情况if(cur last) {cur.prev.next cur.next;last last.prev;return;}//要删除的节点是中间的节点的情况cur.prev.next cur.next;cur.next.prev cur.prev;return;}else {cur cur.next;}}System.out.println(该节点不存在);}链表置空 方式一 headnull; lastnull;方式二 1.使用cur局部变量遍历链表将每一个节点都置为null 2.将头节点和尾节点置为空 public void clear() {ListNode cur this.head;while (cur ! null) {ListNode curNext cur.next;//如果是引用类型还需要将数值域置为空
// cur.val null;cur.prev null;cur.next null;cur curNext;}head null;last null;}【完整代码】 双向、不带头节点、非循环链表的实现LinkedList .class
public class LinkedList2 implements IList {static class ListNode {public int val;//数值域public ListNode next;//指针域指向下一个节点public ListNode prev;//指针域指向前一个节点public ListNode(int val) {this.val val;}}public ListNode head;public ListNode last;Overridepublic void addFirst(int data) {ListNode node new ListNode(data);if (head null) {head node;last node;} else {node.next head;head.prev node;head node;}}Overridepublic void addLast(int data) {ListNode node new ListNode(data);if (head null) {head node;last node;} else {last.next node;node.prev last;last node;}}Overridepublic void addIndex(int index, int data) {int len size();//index小于0或者大于链表的长度插入位置不合法if (index 0 || index len) {throw new IndexOutOfBounds(要插入的位置小于0或者超过链表的长度该位置不合法);}//如果在第一个节点插入使用头插法if (index 0) {addFirst(data);return;}//如果在最后一个节点插入使用尾插法if (index len) {addLast(data);return;}//中间位置//获取要插入的位置的节点ListNode cur getNode(index);//新插入的节点ListNode node new ListNode(data);//在中间位置插入节点元素ListNode curPrev cur.prev;curPrev.next node;node.next cur;node.prev curPrev;cur.prev node;}public ListNode getNode(int index) {ListNode cur this.head;while (index ! 0) {index--;cur cur.next;}return cur;}Overridepublic boolean contains(int key) {ListNode cur head;while (cur ! null) {if (cur.val key) {return true;}cur cur.next;}return false;}Overridepublic void remove(int key) {ListNode cur this.head;while (cur ! null) {//判断是否找到目标节点if (cur.val key) {//要删除的节点是头节点的情况if (cur head) {head head.next;//链表中只有头节点一个节点,删除之后链表为空链表last需要置为nullif (head null) {last null;} else {//链表中不止一个节点需要将头节点的prev置为nullhead.prev null;}} else if (cur last) {//要删除的节点是尾节点的情况cur.prev.next cur.next;last last.prev;} else {//要删除的节点是中间的节点的情况cur.prev.next cur.next;cur.next.prev cur.prev;}return;} else {cur cur.next;}}System.out.println(该节点不存在);}Overridepublic void removeAllKey(int key) {ListNode cur this.head;while (cur ! null) {//判断是否找到目标节点if (cur.val key) {//要删除的节点是头节点的情况if (cur head) {head head.next;//链表中只有头节点一个节点,删除之后链表为空链表last需要置为nullif (head null) {last null;} else {//链表中不止一个节点需要将头节点的prev置为nullhead.prev null;}} else if (cur last) {//要删除的节点是尾节点的情况cur.prev.next cur.next;last last.prev;} else {//要删除的节点是中间的节点的情况cur.prev.next cur.next;cur.next.prev cur.prev;}cur cur.next;}System.out.println(该节点不存在);}}Overridepublic int size() {int count 0;ListNode cur head;while (cur ! null) {cur cur.next;count;}return count;}Overridepublic void clear() {ListNode cur this.head;while (cur ! null) {ListNode curNext cur.next;
// cur.val null;cur.prev null;cur.next null;cur curNext;}head null;last null;}Overridepublic void display() {ListNode cur head;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}
}4.LinkedList的使用
4.1 什么是LinkedList
LinkedList 的官方文档 LinkedList的底层是双向链表结构(链表后面介绍)由于链表没有将元素存储在连续的空间中元素存储在单独的节点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。 在集合框架中LinkedList也实现了List接口具体如下 【说明】 1. LinkedList实现了List接口 2. LinkedList的底层使用了双向链表 3. LinkedList没有实现RandomAccess接口因此LinkedList不支持随机访问 4. LinkedList的任意位置插入和删除元素时效率比较高时间复杂度为O(1) 5. LinkedList比较适合任意位置插入的场景 4.2 LinkedList的使用
4.2.1. LinkedList的构造
方法解释LinkedList()无参构造public LinkedList(Collection? extends E c)使用其他集合容器中元素构造List
public static void main(String[] args) {// 构造一个空的LinkedListListInteger list1 new LinkedList();ListString list2 new java.util.ArrayList();list2.add(JavaSE);list2.add(JavaWeb);list2.add(JavaEE);// 使用ArrayList构造LinkedListListString list3 new LinkedList(list2);
}4.2.2. LinkedList的其他常用方法介绍
方法解释boolean add(E e)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection? extends E c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标List subList(int fromIndex, int toIndex)截取部分 list
public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 删除第一个元素内部调用的是removeFirst()list.removeFirst(); // removeFirst(): 删除第一个元素list.removeLast(); // removeLast(): 删除最后元素list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在如果存在返回true否则返回falseif(!list.contains(1)){list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置int elem list.get(0); // get(index): 获取指定位置元素list.set(0, 100); // set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回ListInteger copy list.subList(0, 3); System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());
}4.2.3. LinkedList的遍历
public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());//方式一 foreach遍历for (int e:list) {System.out.print(e );}System.out.println();//方式二for循环for (int i 0;i list.size();i) {System.out.print(list.get(i) );}System.out.println();//方式三迭代器// 使用迭代器遍历---正向遍历ListIteratorInteger it list.listIterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();// 使用反向迭代器---反向遍历ListIteratorInteger rit list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() );}System.out.println();
}5. ArrayList和LinkedList的区别
不同点ArrayListLinkedList存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)头插需要搬移元素效率低O(N)只需修改引用的指向时间复杂度为O(1)插入空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁 如果是经常根据下标进行查找使用顺序表ArrayList如果是经常插入和删除操作的可以使用链表LinkedList
