亿万网站,网站设计公司皆选奇点网络,河南省住房和城乡建设厅,湖南网站建设优化1.概念及结构 链表是一种 物理存储结构上非连续 存储结构#xff0c;数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。 2.分类 链表的结构非常多样#xff0c;以下情况组合起来就有 8 种链表结构#xff1a; #xff08;1#xff09;单向或者双向 #xff08;…1.概念及结构 链表是一种 物理存储结构上非连续 存储结构数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。 2.分类 链表的结构非常多样以下情况组合起来就有 8 种链表结构 1单向或者双向 2带头或者不带头 3循环或者不循环 即单向带头循环链表、单向不带头循环链表、单向带头不循环链表、单向不带头不循环链表、双向带头循环链表、双向不带头循环链表、双向带头不循环链表和双向不带头不循环链表。 虽然有这么多的链表的结构但是我们本篇主要讲两种 : 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。无头双向非循环链表在Java的集合框架库中LinkedList底层实现就是无头双向非循环链表。 3. 代码实现 3.1 无头单向非循环链表 3.1.1 节点结构 static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val val;}} 3.1.2 方法接口 public interface ISingleLinkedList {
//头插法
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()
} 3.1.3 功能实现 public class MySingleLinkedList implements IMySingleLinkedList {Overridepublic void addFirst(int data) {ListNode node new ListNode(data);node.next head;head node;}Overridepublic void addLast(int data) {ListNode node new ListNode(data);if(head null) {head node;return;}ListNode cur head;while (cur.next ! null) {cur cur.next;}cur.next node;}Overridepublic void addIndex(int index,int data) {//1.判断index的合法性try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}//2.index 0 || index size()if(index 0) {addFirst(data);return;}if(index size()) {addLast(data);return;}//3. 找到index的前一个位置ListNode cur findIndexSubOne(index);//4. 进行连接ListNode node new ListNode(val);node.next cur.next;cur.next node;}private ListNode findIndexSubOne(int index) {int count 0;ListNode cur head;while (count ! index-1) {cur cur.next;count;}return cur;}private void checkIndex(int index) throws IndexNotLegalException{if(index 0 || index size()) {throw new IndexNotLegalException(index不合法);}}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) {if(head null) {return;}if(head.val key) {head head.next;return;}ListNode cur head;while (cur.next ! null) {if(cur.next.val key) {ListNode del cur.next;cur.next del.next;return;}cur cur.next;}}Overridepublic void removeAllKey(int key) {//1. 判空if(this.head null) {return;}//2. 定义prev 和 curListNode prev head;ListNode cur head.next;//3.开始判断并且删除while(cur ! null) {if(cur.val key) {prev.next cur.next;}else {prev cur;}cur cur.next;}//4.处理头节点if(head.val key) {head head.next;}}Overridepublic int size(){int count 0;ListNode cur head;while (cur ! null) {count;cur cur.next;}return count;}Overridepublic void clear() {//head null;ListNode cur head;while (cur ! null) {ListNode curN cur.next;//cur.val null;cur.next null;cur curN;}head null;}Overridepublic void display() {ListNode cur head;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}
}//自定义异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
} 3.2 无头双向非循环链表 3.2.1 节点结构 class ListNode {public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val) {this.val val;}} 3.2.2 方法接口 public interface IMyLinkedList {
//头插法
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();
} 3.2.3 功能实现 public class MyLinkedList implements IMyLinkedList {public ListNode head;//标志头节点public ListNode last;//标志尾结点//头插法Overridepublic void addFirst(int data){ListNode node new ListNode(data);if(head null) {//是不是第一次插入节点head 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 last node;}else {last.next node;node.prev last;last last.next;}}//任意位置插入,第一个数据节点为0号下标Overridepublic void addIndex(int index,int data){try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}if(index 0) {addFirst(data);return;}if(index size()) {addLast(data);return;}//1. 找到index位置ListNode cur findIndex(index);ListNode node new ListNode(data);//2、开始绑定节点node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;}private ListNode findIndex(int index) {ListNode cur head;while (index ! 0) {cur cur.next;index--;}return cur;}private void checkIndex(int index) {if(index 0 || index size()) {throw new IndexNotLegalException(双向链表插入index位置不合法: index);}}//查找是否包含关键字key是否在单链表当中Overridepublic boolean contains(int key){ListNode cur head;while (cur ! null) {if(cur.val key) {return true;}cur cur.next;}return false;}//删除第一次出现关键字为key的节点Overridepublic void remove(int key){ListNode cur head;while (cur ! null) {if(cur.val key) {//开始删除 处理头节点if(cur head) {head head.next;if(head ! null) {head.prev null;}else {last null;}}else {cur.prev.next cur.next;if(cur.next null) {//处理尾巴节点last last.prev;}else {cur.next.prev cur.prev;}}return;//删完一个就走}cur cur.next;}}//删除所有值为key的节点Overridepublic void removeAllKey(int key){ListNode cur head;while (cur ! null) {if(cur.val key) {//开始删除 处理头节点if(cur head) {head head.next;if(head ! null) {head.prev null;}else {//head null 证明只有1个节点last null;}}else {cur.prev.next cur.next;if(cur.next null) {//处理尾巴节点last last.prev;}else {cur.next.prev cur.prev;}}}cur cur.next;}}//得到双向链表的长度Overridepublic int size(){int count 0;ListNode cur head;while (cur ! null) {count;cur cur.next;}return count;}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 curN cur.next;//cur.val null;cur.prev null;cur.next null;cur curN;}head last null;}
}
//自定义异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
} 4.LinkedList 4.1 概念 LinkedList 的底层是双向链表结构 ( 链表后面介绍 ) 由于链表没有将元素存储在连续的空间中元素存储在单独的节点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。 注意 1. LinkedList 实现了 List 接口 2. LinkedList 的底层使用了双向链表 3. LinkedList 没有实现 RandomAccess 接口因此 LinkedList 不支持随机访问 4. LinkedList 的任意位置插入和删除元素时效率比较高时间复杂度为 O(1) 5. LinkedList 比较适合任意位置插入的场景 4.2 使用 4.2.1 构造方法 方法说明 LinkedList() 无参构造public LinkedList(Collection? extends E c)使用其他集合容器中元素构造List 代码示例 public static void main(String[] args) {// 构造一个空的LinkedListListString list1 new LinkedList();list1.add(sas);list1.add(asd);list1.add(Jsd);System.out.print(list1: );for(int i 0; i list1.size();i){System.out.print(list1.get(i) );}System.out.println();System.out.print(list2: );ListString list2 new LinkedList(list1);for(int i 0; i list2.size();i){System.out.print(list2.get(i) );}} 运行结果如下 4.2.2 其他常用方法 方法解释 boolean add( E e) 尾插 e void add(int index, E element) 将 e 插入到 index 位置 boolean addAll(Collection? extends E c) 尾插 c 中的元素 E remove(int index) 删除 index 位置元素 boolean remove(Object o) 删除遇到的第一个 o E get(int index) 获取下标 index 位置元素 E set(int index, E element) 将下标 index 位置元素设置为 element void 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); // 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.3 遍历 我们之前常用的遍历方式有for循环、foreach循环和while循环等来进行遍历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);// 使用迭代器遍历---正向遍历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) 插入 空间不够时需要扩容没有容量的概念 应用场景 元素高效存储频繁访问任意位置插入和删除频繁 本文是作者学习后的总结如果有什么不恰当的地方欢迎大佬指正
