1.基本结构:
双向链表是一种链表数据结构,它由一系列节点组成,每个节点包含三个部分:
(1).数据域:存储节点的数据
(2).前驱指针:指向前一个节点
(3).后驱指针:指向下一个节点
2.基本特性:
双向链接: 与单向链表不同,双向链表的每个节点都可以向前和向后移动,这使得在链表中插入和删除节点更加灵活。
3.基本操作:
我们要实现的功能:
addFirst(头插) 、 addLast(尾插)、disPlay(展示)、size(数组长度)、contains(是否包含某个元素)、 index(在某个节点处插入某个元素)、remove(移除某个元素)、removeAllKey(移除所有符合元素)、clear(清除所有数据),当然这些方法都要在接口List中都要进行定义。
3.0 双向链表基本结构的实现:
(1).包含基本结构:数据域、前驱指针、后驱指针
(2) 构造方法的实现:每个数据域对应的值输入(整数)
(3). 头节点、尾节点的定义。
具体代码如下:
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; //尾节点
3.1 头插方法的实现:
1.创建一个node 节点
2.判断头节点是否为空(链表是否为空),为空的话,将头尾节点均置为空。
3. 插入元素:将node.next = head, head.prev = node
head = node;(更新头节点)
具体代码如下:
public void addFirst(int data) {ListNode node = new ListNode(data);if(head == null){head = last = null;}else{node.next = head;head.prev = node;head = node;}}
3.2 尾插方法的实现:
1.创建一个新节点node储存新元素
2.判断头节点是否为空
3.插入元素:具体代码如下:
@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null){head = last = null;}else{last.next = node;node.prev = last;last = last.next;}}
3.3 disPlay方法的实现:
1.创建新节点cur 来保存头节点。
2.while循环遍历打印元素,同时更新cur节点
具体代码如下:
public void disPlay() {ListNode cur = head;while(cur!=null){System.out.println(cur.val);cur = cur.next;}System.out.println();}
3.4 size()方法的实现:
1.创建一个保存头节点的cur节点,以及一个用于记录整形的变量len,while循环,每次len++ 并更新cur节点,最后返回len的值。
具体代码如下:
@Overridepublic int size() {int len = 0;ListNode cur = head;while(cur!=null){len++;cur = cur.next;}return len;}
3.5 contains方法的实现:
1.创建一个新节点cur来保存头节点
2.while循环,遍历过程中判断data是否 == cur.val,是的话,返回true,否则返回false,具体代码如下:
public boolean contains(int key) {ListNode cur = head;while(cur!=null){if(cur.val == key){return true;}cur = cur.next;}return false;}
3.6:index方法的实现:
1.判断给出的index位置是否合理:<0/ >len(链表长度),返回。
2.若index == 0,头插, index == len,尾插
3.创建findIndex方法,找到位于index位置处的节点。
ListNode cur = head,while循环(index不为0)遍历cur进入下一个节点,同时index自减1,
循环结束返回cur。 具体代码如下:
private ListNode findIndex(int index){ListNode cur = head;while( index !=0){cur = cur.next; //到达index位置处index--;}return cur;}
4.插入 node节点:
3.7 remove方法的实现:
创建一个cur节点来存储head节点,while循环cur!=null,循环结束cur要更新至下一个节点
1.头删的实现:
2.尾删的情况:
3.中间情况的实现
具体代码实现:
public void remove(int key) {ListNode cur = head;while(cur!=null){if(cur.val == key){if(cur == head){head = head.next;if(cur!=null){cur.prev = null;}else{cur.prev.next = cur.next;if(cur.next == null){last = last.prev;}else{cur.next.prev = cur.prev;}}return ;}cur = cur.next;}}}
3.8 removeAllkey方法的实现:
将remove方法中的return去掉即可,这样消除了一个元素后可以继续遍历循环删除。
3.9 clear方法的实现:
创建新节点cur储存head,while循环遍历链表,设置curN节点为cur的下一个节点,在cur清除当前节点元素后,cur = curN, cur进入下一个位置即curN,进入下一次循环后curN再次后移。
最后,遍历结束后head节点和尾节点要手动置为null。
具体代码如下:
@Overridepublic void clear() {ListNode cur = head;while(cur!=null){ListNode curN = cur.next;cur.next = null;cur.prev = null;cur = curN;}head = last = null;}
}
今天分享结束,喜欢的老来个三联把!