免费网站模板之家,网站建设前期需要准备什么资料,网站制作公司多少钱一年,网页设计素材怎么放进去目录
一、Arraylist的缺陷
二、链表 2.1 链表的概念和结构 2.2 链表的实现
三、链表面试题 3.1 删除链表中所有值为val的节点 3.2 反转一个单链表 3.3 链表的中间节点 3.4 将有序链表合并 3.5 输出倒数第k个节点 3.6 链表分割 3.7 链表的回文结构 3.8 找两个链表的公共节…目录
一、Arraylist的缺陷
二、链表 2.1 链表的概念和结构 2.2 链表的实现
三、链表面试题 3.1 删除链表中所有值为val的节点 3.2 反转一个单链表 3.3 链表的中间节点 3.4 将有序链表合并 3.5 输出倒数第k个节点 3.6 链表分割 3.7 链表的回文结构 3.8 找两个链表的公共节点 3.9 判断链表是否有环 3.10 找链表入环的第一个节点
四、LinkedList的模拟实现
五、LinkedList的使用 5.1 什么是LinkedList 5.2 LinkedList的使用
六、ArrayList和LinkedList的区别 一、Arraylist的缺陷 ArrayList底层使用数组来存储元素 public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.Serializable { // ... // 默认容量是10 private static final int DEFAULT_CAPACITY 10; //... // 数组用来存储元素 transient Object[] elementData; // 有效元素个数 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底层是一段连续空间当在ArrayList任意位置插入或者删除元素时需要将后序元素整体往前或者往后搬移时间复杂度为O(n)效率比较低因此ArrayList不适合做任意位置插入和删除比较多的场景。因此java集合中引入LinkedList即链表结构。
二、链表 2.1 链表的概念和结构 链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的。 链式结构在逻辑上连续但在物理上不一定连续节点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续。 实际中的链表结构非常多以下请况组合起来就有8种 1. 单向或双向 2. 带头或不带头 3. 循环或非循环 链表有很多重点掌握两种 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多 无头双向链表在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 2.2 链表的实现 //无头单向非循环链表实现 public class SingleLinkedList { //头插法 public void addFirst(int data){ } //尾插法 public void addLast(int data){ } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ return false; } //删除第一次出现关键字为key的节点 public void remove(int key){ } //删除所有值为key的节点 public void removeAllKey(int key){ } //得到单链表的长度 public int size(){ return -1; } //清空 public void clear() { } //打印 public void display() { } } 三、链表面试题 3.1 删除链表中所有值为val的节点 删除链表中等于给定值val的所有节点 链接 public class ListNode { int val; ListNode next; ListNode() {} ; ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } } 解法1遍历整个链表将其中值为val的节点删除将要删除节点前的节点的next指向要删除节点后的第一个节点。 public ListNode removeElements(ListNode head, int val) { //原链表是空链表 if(headnull) return head; ListNode curhead; //从第二个节点判断 while(cur.next!null){ //下一个节点的值 if(cur.next.valval){ cur.nextcur.next.next; } else{ curcur.next; } } //判断头节点 if(head.valval){ headhead.next; } return head; } 解法2遍历整个链表将所有值不是给定值val的节点放入新链表中返回新链表。 public ListNode removeElements(ListNode head, int val) { //原链表是空链表 if(headnull) return head; //新链表的头节点 ListNode head1new ListNode(); //新链表的节点 ListNode cur1head1; //原来链表的节点 ListNode curhead; //遍历原来链表 while(cur!null){ //当前节点的值 if(cur.valval) curcur.next; else{ cur1.nextcur; curcur.next; cur1cur1.next; } } //如果新链表的尾节点不是原来链表的尾节点将next置空 if(cur1.next!null) cur1.nextnull; return head1.next; } 3.2 反转一个单链表 链接 public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } } public ListNode reverseList(ListNode head) { //原链表为空 if(headnull) return null; //原链表只有一个节点 if(head.nextnull) return head; //原链表的第二个节点开始 ListNode curhead.next; head.nextnull; //遍历链表 while(cur!null){ //curNext为当前节点的下一个节点 ListNode curNextcur.next; //头插法插入节点 cur.nexthead; headcur; //当前节点指向原链表位置的下一个节点 curcurNext; } return head; } 3.3 链表的中间节点 给一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点 链接 public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } } 解法1先求链表长度获取长度一半的节点 public ListNode middleNode(ListNode head) { ListNode curhead; //链表的长度 int count0; while(cur!null){ curcur.next; count; } int BinaCountcount/2; ListNode rethead; for(int i0;iBinaCount;i){ retret.next; } return ret; } 缺陷需要两次遍历才能找到中间节点当节点较多时时间复杂度较大。 解法2在一次遍历中找到中间节点两个引用fast和slow分别走两步和一步 public ListNode middleNode(ListNode head) { ListNode fasthead; ListNode slowhead; while(fast!nullfast.next!null){ fastfast.next.next; slowslow.next; } return slow; } 3.4 将有序链表合并 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的 链接 public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } } public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode NewHeadnew ListNode(); //Newcur 新链表的尾节点 ListNode NewcurNewHead; while(list1!nulllist2!null){ if(list1.vallist2.val){ Newcur.nextlist1; list1list1.next; }else{ Newcur.nextlist2; list2list2.next; } NewcurNewcur.next; } //list1还有数 if(list1!null){ Newcur.nextlist1; } //list2还有数 if(list2!null){ Newcur.nextlist2; } return NewHead.next; } 3.5 输出倒数第k个节点 输入一个链表输出该链表中倒数第k个结点 链接 public ListNode FindKthToTail(ListNode head,int k) { //链表为空或k太小 if(k0||headnull){ return null; } ListNode fasthead; //fast指向第k个节点 while(k1){ fastfast.next; //当k太大 if(fastnull){ return null; } k--; } ListNode slowhead; //fast没有指向最后一个节点 while(fast.next!null){ fastfast.next; slowslow.next; } return slow; } 3.6 链表分割 编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前 链接 public class ListNode { int val; ListNode next null; ListNode(int val) { this.val val; } } public ListNode partition(ListNode pHead, int x) { //pmin链表存小于x的节点 ListNode pmin null; //pin为pmin的尾节点 ListNode pin null; //pmin链表存大于等于x的节点 ListNode pmax null; //pax为pmax的尾节点 ListNode pax null; //遍历链表pHead将小于x和大于等于x的存入pmin和pmax中 ListNode cur pHead; while (cur ! null) { if (cur.val x) { if (pmin null) { //pmin为空 pmin cur; pin cur; } else { //pmin不为空 pin.next cur; pin pin.next; } } else { if (pmax null) { //pmax为空 pmax cur; pax cur; } else { //pmax不为空 pax.next cur; pax pax.next; } } cur cur.next; } if(pminnull){ //没有小于x的 return pmax; } if(pmaxnull){ //没有大于等于x的 return pmin; } //将pmin与pmax串联起来pmin的尾节点指向pmax的头节点 pin.nextpmax; if(pax.next!null){ pax.nextnull; } return pmin; } 3.7 链表的回文结构 链接 public class ListNode { int val; ListNode next null; ListNode(int val) { this.val val; } } 反转 public boolean chkPalindrome(ListNode A) { ListNode fast A; //1、找中间节点slow ListNode slow A; while (fast ! null fast.next ! null) { fast fast.next.next; slow slow.next; } //2、中间节点之后的反转 //cur是节点后的第一个节点 ListNode cur slow.next; slow.nextnull; while (cur! null) { //保存cur后的第一个节点 ListNode curNext cur.next; cur.next slow; slow cur; cur curNext; } //反转结束后slow指向最后一个节点 //3、从第一个节点开始判断 cur A; while (cur ! slow cur.next ! slow) { if (cur.val ! slow.val) { return false; } else { cur cur.next; slow slow.next; } } return true; } 3.8 找两个链表的公共节点 输入两个链表找出它们的第一个公共结点 链接 public class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } } public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //lenA、lenB分别为链表headA和链表headB的长度 int lenA 0; int lenB 0; ListNode curA headA; ListNode curB headB; while(curA ! null){ lenA; curA curA.next; } while( curB ! null){ lenB; curB curB.next; } //pl指向最长链表ps指向最短链表 ListNode pl headA; ListNode ps headB; //长度差值len int len lenA-lenB; if(len0){ //修正pl、ps、len pl headB; ps headA; len lenB-lenA; } //pl走差值步 while(len0){ pl pl.next; len--; } //同步走 while(pl ! ps){ pl pl.next; ps ps.next; } //pl为空没有公共节点 if(pl null){ return null; } return pl; } 3.9 判断链表是否有环 给定一个链表判断链表中是否有环 链接 class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } } public boolean hasCycle(ListNode head) { //快慢指针 ListNode fast head; ListNode slow head; while(fast!nullfast.next!null){ fastfast.next.next; slowslow.next; //相遇-有环 if(fastslow){ return true; } } //循环结束-无环 return false; } 3.10 找链表入环的第一个节点 给定一个链表返回链表开始入环的第一个节点 如果链表无环则返回 NULL 链接 class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } } public ListNode detectCycle(ListNode head) { //快慢指针 ListNode fasthead; ListNode slowhead; //找相遇节点 while(fast!nullfast.next!null){ fastfast.next.next; slowslow.next; //相遇 if(fastslow){ break; } } //fastnull或fast.nextbull-链表不为环也就没有入环的第一个节点 if(fastnull||fast.nextnull){ return null; } //慢指针从头开始 slowhead; while(slow!fast){ slowslow.next; fastfast.next; } //循环结束slow和fast都指向入环的第一个节点 return slow; } 结论让一个指针从链表起始位置开始走同时让一个指针从判环时相遇点的位置开始走两个指针每次均走一步最终肯定会在环的入口点的位置相遇。
四、LinkedList的模拟实现 无头双向链表实现 public class MyLinkedList { //头插法 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 display (){} //清空链表 public void clear (){} } //无头双向链表的操作
public interface IOPeration {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public boolean 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 display();//清空链表public void clear();
} public class MySidesLinkList implements IOPeration{static class ListNode {int val;ListNode pre;ListNode next;public ListNode(int data){valdata;}}private int usedSize;private ListNode head;private ListNode last;Overridepublic void addFirst(int data) {ListNode node new ListNode(data);if(head null){head node;last node;}else {node.next head;head.pre node;head node;}usedSize;}Overridepublic void addLast(int data) {ListNode node new ListNode(data);if(last null){head node;last node;}else {last.next node;node.pre last;last node;}usedSize;}Overridepublic boolean addIndex(int index, int data) {if(index0||indexusedSize){throw new IndexEception(下标异常index);}if(index 0){addFirst(data);return true;}if(index usedSize){addLast(data);return true;}ListNode curhead;while(index0){cur cur.next;index--;}ListNode node new ListNode(data);cur.pre.next node;node.nextcur;node.pre cur.pre;cur.pre node;usedSize;return true;}Overridepublic boolean contains(int key) {ListNode cur head;while(cur ! null){if(cur.val key){return true;}else {curcur.next;}}return false;}Overridepublic void remove(int key) {ListNode cur head;while(cur ! null){if(cur.val key){if(cur head){head head.next;head.pre null;cur.next null;}else if(cur last){last last.pre;last.next null;cur.pre null;}else {cur.pre.next cur.next;cur.next.pre cur.pre;}usedSize--;return;}else {cur cur.next;}}}Overridepublic void removeAllKey(int key) {ListNode cur head;while(cur ! null){if(cur.val key){ListNode curNextcur.next;if(cur head){head head.next;head.pre null;cur.next null;}else if(cur last){last last.pre;last.next null;cur.pre null;}else {cur.pre.next cur.next;cur.next.pre cur.pre;}usedSize--;curcurNext;}else {cur cur.next;}}}Overridepublic int size() {return usedSize;}Overridepublic void display() {ListNode cur head;while (cur ! null){System.out.print(cur.val );cur cur.next;}System.out.println();}Overridepublic void clear() {ListNode cur head;while (cur ! null){ListNode curNext cur.next;cur.pre null;cur.next null;curcurNext;}head null;last null;}
}//下标异常类
public class IndexEception extends RuntimeException{public IndexEception (String massage){super(massage);}
} 五、LinkedList的使用 5.1 什么是LinkedList LinkedList的底层是双向链表结构链表没有将元素存储在连续空间中而是存储在单独的节 点中通过引用将节点连接起来了因此在任意位置插入或者删除元素时不需要搬移元素效率较高。 在集合框架中LinkedList也实现了List接口 LinkedList实现了List接口底层使用双向链表没有实现RandomAccess接口不支持随机访问LinkedList在任意位置插入和删除效率较高时间复杂度为O(1);适合任意位置插入的场景。 5.2 LinkedList的使用 1. LinkedList的构造
方法解释 public LinkedList(); 无参构造public LinkedList(Collection? extends E c)使用其他集合容器中元素构造List public static void main(String[] args) {LinkedListInteger list1 new LinkedList();list1.addLast(1);list1.addLast(2);list1.addLast(3);//打印链表for (Integer x:list1) {System.out.print(x );}System.out.println();/*使用list1中的元素构造list2* 其中list1的类型是与list2是同类型或是list2的子类类型* 存储元素的类型保持一致*/LinkedListInteger list2 new LinkedList(list1);//打印链表for (Integer x:list2) {System.out.print(x );}System.out.println();
} 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 的下标ListE subList(int fromIndex, int toIndex) 截取部分 list public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);//尾插list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list.size()); //5System.out.println(list); //[1, 2, 3, 4, 5]System.out.println();list.add(2,10);//在 index 位置插入元素list.addFirst(10);//头插list.addLast(10);//尾插System.out.println(list); //[10, 1, 2, 10, 3, 4, 5, 10]System.out.println();list.remove();//默认删除第一个元素System.out.println(list); //[1, 2, 10, 3, 4, 5, 10]list.removeFirst();//删除第一个元素System.out.println(list); //[2, 10, 3, 4, 5, 10]list.removeLast();//删除最后一个元素System.out.println(list); //[2, 10, 3, 4, 5]list.remove(1);//删除index位置的元素System.out.println(list); //[2, 3, 4, 5]System.out.println();//containselem判断elem元素是否存在System.out.println(list.contains(5));//true//从前向后找第一个elem出现的位置System.out.println(list.indexOf(3));//从后向前找第一个elem出现的位置System.out.println(list.lastIndexOf(4));System.out.println();//获取index位置的元素int elem list.get(0);//set设置index位置的值为elemlist.set(0,100);System.out.println(list); //[100, 3, 4, 5]System.out.println();//subList截取部分(左闭右开)并返回返回值类型为ListEListInteger list2 list.subList(0,2);System.out.println(list2); //[100, 3]
}3. LinkedList的遍历 public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);//遍历链表//foreach遍历for (int x:list) {System.out.print(x );//1 2 3 4 5}System.out.println();//迭代器遍历ListIteratorInteger it list.listIterator();while (it.hasNext()){System.out.print(it.next() );//1 2 3 4 5}System.out.println();//反向迭代器遍历ListIteratorInteger reverseIt list.listIterator(list.size());while (reverseIt.hasPrevious()){System.out.print(reverseIt.previous() );//5 4 3 2 1 }
} 六、ArrayList和LinkedList的区别 不同点ArrayListLinkedList存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)头插需要移动元素效率低O(N)只需修改引用的指向O(1)插入空间不够需要扩容没有容量的概念应用场景元素高效存储、频繁访问任意位置插入和删除频繁
