廊坊企业网站服务,高端品牌灯具,wordpress用的编辑器,百度收录左侧带图片的网站1.LinkedList的介绍和结构 LinkedList的底层是双向链表结构#xff0c;相对于之前的单向无头非循环链表来说#xff0c;LinkedList最大的区别就是该链表可以增加了一条链接逻辑#xff0c;可以从最后一个节点通过地址访问来到整个链表的头结点。 通过以下集合框架#xff0…1.LinkedList的介绍和结构 LinkedList的底层是双向链表结构相对于之前的单向无头非循环链表来说LinkedList最大的区别就是该链表可以增加了一条链接逻辑可以从最后一个节点通过地址访问来到整个链表的头结点。 通过以下集合框架LinkedList也实现了List接口具体如下 注意 1. LinkedList 实现了 List 接口 2. LinkedList 的底层使用了双向链表 3. LinkedList 没有实现 RandomAccess 接口因此 LinkedList 不支持随机访问 4. LinkedList 的任意位置插入和删除元素时效率比较高时间复杂度为 O(1) 5. LinkedList 比较适合任意位置插入的场景 1.1 LinkedList的结构 双向无头非循环链表的节点是由三部分构成的用来存储数据的value域存放下一个节点地址的next域以及用来存放前一个节点地址的prev域其节点和链表结构如下图所示 简单要点如下 2.无头双向非循环链表的实现
2.1 自定义MyLinkedList类 1、建立一个Ilist接口在里面构造mylinkedlist链表要实现的抽象方法
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();
} 无头双向非循环链表的节点是由三个属性value域、prev域和next域构成的同时也要在自定义MyLinkedList类里面使用内部类创建链表节点类之后在链表类里面创建一个头结点head来代表当前链表的引用同时创建一个节点last来表示当前链表的最后一个节点同时让该自定义类实现我们之前创建的接口接下来重写接口里面的方法让其能够具体化
public class MyLinkedList implements IList {static class ListNode {public int value;public ListNode prev;public ListNode next;public ListNode(int value) {this.value value;}}public ListNode head;public ListNode last;Overridepublic void addFirst(int data) {}Overridepublic void addLast(int data) {}Overridepublic void addIndex(int index, int data) {}Overridepublic boolean contains(int key) {return false;}Overridepublic void remove(int key) {}Overridepublic void removeAllKey(int key) {}Overridepublic int size() {return 0;}Overridepublic void clear() {}Overridepublic void display() {}
}
2.2头插法 思路图解如下 1、如果是空链表头节点head为null则要添加的节点node就是头节点也是尾节点. 2、头节点不为null 2.1 将原先head的前驱节点指向新增节点位置新增节点后驱节点指向head节点的位置注意和新节点建立连接一定要从前往后建立 2.2 head指向新增节点位置新的链表的第一个节点为head。
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;}} 执行结果在2.3中
2.3 遍历链表 思路与mysinglelist链表的相同这里略代码如下
Overridepublic void display() {ListNode cur head;while (cur ! null){System.out.print(cur.value-);cur cur.next;}System.out.println( );}public static void main(String[] args) {MyLinkedList myLinkedList new MyLinkedList();myLinkedList.addFirst(1);myLinkedList.addFirst(0);
// myLinkedList.addFirst(2);myLinkedList.display();} 执行结果如下 2.4尾插法 思路 1、如果是空链表头节点head为null则要添加的节点node就是头节点也是尾节点. 2、头节点不为null 2.1 将原先last的后驱节点last.prev指向新增节点node位置新增节点前驱节点指向last节点的位置注意和新节点建立连接一定要从前往后建立 2,2将node节点改为新的last节点 代码和测试结果如下
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;}}
public static void main(String[] args) {MyLinkedList myLinkedList new MyLinkedList();myLinkedList.addFirst(1);myLinkedList.addFirst(0);myLinkedList.display();myLinkedList.addLast(7);myLinkedList.addLast(8);myLinkedList.display();} 2.5 链表长度 对整个链表进行遍历使用计数器进行记录遍历的次数最后将计数器的值返回即可下图代码是该方法的具体实现 Overridepublic int size() {int count 0;ListNode cur head;while (cur ! null){count;curcur.next;}return count;}
public static void main(String[] args) {MyLinkedList myLinkedList new MyLinkedList();myLinkedList.addFirst(1);myLinkedList.addFirst(0);myLinkedList.display();myLinkedList.addLast(7);myLinkedList.addLast(8);myLinkedList.display();System.out.println(myLinkedList.size());} 测试结果如下 2.6 任意位置插入 思路 1、需要插入的位置必须为合法如果不合法我们会抛出一个异常进行提醒所以首先自定义一个异常
public class ListIndexOutOfException extends RuntimeException{public ListIndexOutOfException() {}public ListIndexOutOfException(String message) {super(message);}
} 2、任意位置插入首先分几种情况插在开头插在结尾插在中间 2.1 当插在链表开头和结尾时可以使用头插法和尾差法 2.2 如下图所示按照z字形进行赋值和写代码当插在其他的位置时首先让cur走到index的位置此处创建一个方法找到index位置的节点并将这个节点定义为cur返回这时候就需要考虑将下一个节点加在index的位置时如何处理建立连接的顺序其次注意建立连接的时候一定要先建立原index前的节点和node节点添加节点的连接其次再建立添加节点node和原index节点的连接链表图解如下 具体方法代码如下
Overridepublic void addIndex(int index, int data) {ListNode node new ListNode(data);if(index 0 || index size()) {//抛自定义的异常throw new ListIndexOutOfException(你当前输入的索引有问题);}if(index 0) {addFirst(data);return;}if(index size()) {addLast(data);return;}ListNode cur findIndex(index);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){index--;cur cur.next;}return cur;}
public static void main(String[] args) {MyLinkedList myLinkedList new MyLinkedList();myLinkedList.addFirst(1);myLinkedList.addFirst(0);myLinkedList.display();myLinkedList.addLast(7);myLinkedList.addLast(8);myLinkedList.display();System.out.println(myLinkedList.size());myLinkedList.addIndex(3,99);myLinkedList.display();} 2.7 查找关键字 对链表进行遍历然后将关键字key和链表数值进行比较如果存在key关键字则返回true反之则返回false 方法具体实现的代码如下 Overridepublic boolean contains(int key) {ListNode cur head;while (cur ! null) {if (cur.value key) {return true;}cur cur.next;}return false;}
public static void main(String[] args) {MyLinkedList myLinkedList new MyLinkedList();myLinkedList.addFirst(1);myLinkedList.addFirst(0);myLinkedList.addLast(7);myLinkedList.addLast(8);myLinkedList.addIndex(3,99);myLinkedList.display();System.out.println(myLinkedList.contains(1));} 测试代码和执行结果如下 2.8删除第一个关键字为key的节点 思路 1、链表为空链表不用操作 2、删除数据在第一个首先让cur节点移动到第二个节点其次判断新的链表是否只有一个节点 2.1 如果只剩下cur这个节点则让head指向null让last指向null 2.2让cur这个节点的prev指向null其他的不变 3、没有你要删除的数据不用操作 4、有你要删除的数据且不是第一个cur节点是要删除的节点 4.1 删除数据最后一个让last节点往前移一个单位 4.2删除的数据不是最后一个首先让cur的前一个节点的next域直接存cur下一个节点的地址其次让cur下一个节点的prev域存放cur前一个节点的地址 代码如下 Overridepublic void remove(int key) {ListNode cur head;while (cur ! null) {if (cur.value key){if(cur head) {//整个链表的头结点为要删除的节点head head.next;//head nullif(head null) {last null;}else {head.prev null;}}else {//链表的其他节点是要删除的cur.prev.next cur.next;if(cur.next null) {//要删除的是最后一个节点last last.prev;}else {cur.next.prev cur.prev;}}return;}else {cur cur.next;}}}
2.9删除所有值为key的节点 与删除第一次出现关键字为key的节点几乎是一模一样的我们只需要遍历完整个链表将return删掉就好。 代码如下 Overridepublic void removeAllKey(int key) {ListNode cur head;while (cur ! null) {if (cur.value key){if(cur head) {//整个链表的头结点为要删除的节点head head.next;//head nullif(head null) {last null;}else {head.prev null;}}else {//链表的其他节点是要删除的cur.prev.next cur.next;if(cur.next null) {//要删除的是最后一个节点last last.prev;}else {cur.next.prev cur.prev;}}}cur cur.next;}}
2.10清空链表 1、只需要遍历整个链表将每个节点的前驱与后继节点都置为null就好 public void clear(){ListNode cur head;while(cur ! null) {cur.prev null;cur cur.next;cur.prev.next null;}} 2、将链表的首节点和为节点指向null即可 public void clear() {head null;last null;} ps本次内容就到这里了如果你喜欢的话就请一键三连
