网站用oracle做数据库,怀化主要网站,建筑营销型网站,wordpress上传更新链表
链表的概念
链表是一种物理存储结构上非连续的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的引用链接次序实现的。 通俗来说#xff0c;相比较于顺序表#xff08;物理上连续#xff0c;逻辑上也连续#xff09;#xff0c;链表物理上不一定连续。
链表是…链表
链表的概念
链表是一种物理存储结构上非连续的存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的。 通俗来说相比较于顺序表物理上连续逻辑上也连续链表物理上不一定连续。
链表是由一个一个节点组织起来的组织起来的整体就叫做链表。
链表的结构非常多样
1.单向或双向 2.带头或不带头 3.循环或非循环 以上的链表结构可以组成八种链表。
在Java集合框架中的LinkedList底层实现的是无头双向循环链表。
LinkedList模拟实现
1.创建一个无头双向链表并标志头结点个尾结点。 static class ListNode {public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val) {this.val val;}}public ListNode head;//标志头节点public ListNode last;//标志尾结点
2.计算双向链表的长度
从head开始遍历节点到尾结点并定义一个变量count计数。
public int size(){int count 0;ListNode cur head;while (cur ! null) {count;cur cur.next;}return count;}
这里有一个问题为什么遍历的条件是curnull而不是cur.nextnull
我们可以知道此链表的尾结点next位置存的是null如果以cur.nextnull作为判断条件
那么当执行完循环中最后一条语句“cur cur.next;”时此时由于尾结点的next为空所以会跳出循环相当于count少进行了一次计数那么最终的count值就是错误的。
3.查找是否包含关键字key在链表中
public boolean contains(int key){ListNode cur head;while (cur ! null) {if(cur.val key) {return true;}cur cur.next;}return false;}
4.头插法
关键步骤 node.next head; head.prev node; head node; public void addFirst(int data){ListNode node new ListNode(data);if(head null) {//是不是第一次插入节点head last node;}else {node.next head;head.prev node;head node;}}
5.尾插法
关键步骤 last.next node; node.prev last; last last.next; public 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;}} 6.任意位置插入
关键步骤 先记录要插入位置上的节点记为cur然后直接修改指向 node.next cur; cur.prev.next node; node.prev cur.prev; cur.prev node;
注意不能修改代码顺序 public void addIndex(int index,int data){try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}//在0位置插入调用头插法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);}}
7.删除第一次出现关键字为key的节点
关键步骤
1修改前驱指针的next跳过cur cur.prev.next cur.next;
2修改下一个指针的前驱跳过cur cur.next.prev cur.prev; public 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 {//head null 证明只有1个节点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;}} 8.删除所有值为key的节点
与上一个方法类似区别是上一个方法删一个之后就退出。 public 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;}
9.清空链表
public 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;}
LinkedList
什么是LinkedList
LinkedList的底层是双向链表结构由于链表没有将元素存储在连续的空间中元素存储在单独的节 点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。 LinkedList实现了List接口。
LinkedList没有实现RandomAccess接口因此不支持随机访问。
LinkedList的任意位置插入和删除元素时效率比较高时间复杂度为O1
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);
}
LinkedList其他常用方法介绍
方法解释 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
