asp网站建设报告书,网页设计代码的意思,机械加工网名大全,微商怎么做分销LinkedList与链表 1. ArrayList的缺陷2. 链表2.1 链表的概念及结构2.2 链表的实现 3. LinkedList的模拟实现4.LinkedList的使用4.1 什么是LinkedList4.2LinkedList的使用 5. ArrayList和LinkedList的区别 1. ArrayList的缺陷
上节课已经熟悉了ArrayList的使用#xff0c;并且… LinkedList与链表 1. ArrayList的缺陷2. 链表2.1 链表的概念及结构2.2 链表的实现 3. LinkedList的模拟实现4.LinkedList的使用4.1 什么是LinkedList4.2LinkedList的使用 5. ArrayList和LinkedList的区别 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 链表的概念及结构
链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。 实际中链表的结构非常多样
单向或者双向 带头或者不带头 循环或者非循环 虽然有这么多的链表的结构但是我们重点掌握两种:无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多无头双向链表在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2.2 链表的实现
自己实现接口ILIST
public interface IList {//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
}链表实现
public class MySingleList implements IList {//节点的内部类static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val val;}}public ListNode head;//public int usedSize;//可以定义public void createList() {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;this.head node1;}Overridepublic void addFirst(int data) {ListNode node new ListNode(data);if (this.head null) {this.head node;} else {node.next this.head;this.head node;}}Overridepublic void addLast(int data) {ListNode node new ListNode(data);ListNode cur this.head;if (this.head null) {this.head node;} else {//找到尾巴while (cur.next ! null) {cur cur.next;}//cur 现在指向了最后一个节点cur.next node;}}Overridepublic void addIndex(int index, int data) {if (index 0 || index size()) {//抛自定义的异常return;}if (index 0) {addFirst(data);return;}if (index size()) {addLast(data);return;}ListNode cur searchPrev(index);ListNode node new ListNode(data);node.next cur.next;cur.next node;}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.val key) {return true;}cur cur.next;}return false;}Overridepublic void remove(int key) {if (this.head null) {//一个节点都没有 无法删除return;}if (this.head.val key) {this.head this.head.next;return;}//1. 找到前驱ListNode cur findPrev(key);//2、判断返回值是否为空if (cur null) {System.out.println(没有你要删除的数字);return;}//3、删除ListNode del cur.next;cur.next del.next;}/*** 找到关键字key的前一个节点的地址** param key* return*/private ListNode findPrev(int key) {ListNode cur this.head;while (cur.next ! null) {if (cur.next.val key) {return cur;}cur cur.next;}return null;}Overridepublic void removeAllKey(int key) {if (this.head null) {return;}ListNode prev head;ListNode cur head.next;while (cur ! null) {if (cur.val key) {prev.next cur.next;cur cur.next;} else {prev cur;cur cur.next;}}if (head.val key) {head head.next;}}Overridepublic int size() {int count 0;ListNode cur this.head;while (cur ! null) {count;cur cur.next;}return count;}Overridepublic void clear() {ListNode cur head;while (cur ! null) {ListNode curNext cur.next;//cur.val null;cur.next null;cur curNext;}head null;}Overridepublic void display() {ListNode cur this.head;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}/*** 这个是从指定位置开始打印** param newHead*/public void display(ListNode newHead) {ListNode cur newHead;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}
}
3. LinkedList的模拟实现
// 2、无头双向链表实现
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(){}
}4.LinkedList的使用
4.1 什么是LinkedList
LinkedList的底层是双向链表结构(链表后面介绍)由于链表没有将元素存储在连续的空间中元素存储在单独的节点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。 在集合框架中LinkedList也实现了List接口
【说明】
LinkedList实现了List接口LinkedList的底层使用了双向链表LinkedList没有实现RandomAccess接口因此LinkedList不支持随机访问LinkedList的任意位置插入和删除元素时效率比较高时间复杂度为O(1)LinkedList比较适合任意位置插入的场景
4.2LinkedList的使用
LinkedList的构造
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);
}LinkedList的其他常用方法介绍 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();
// 使用迭代器遍历---正向遍历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的区别
