赞
踩
目录
更详细的理论请移步笔者的另一文章
双向链表就是在单链表的基础上加上了一个 prev,存放上一个节点的地址
- public class MyLinkedList {
- // 自己实现双向链表
- static class ListNode {
- int val;
- ListNode prev;//前
- ListNode next;//后
-
- public ListNode(int val) {
- this.val = val;
- }
- }
-
- ListNode head = null;//头
- ListNode last = null;//尾
- }
需要什么方法在后续再补充
可正序打印
也可逆序打印
- public void printHead() {
- //正序打印
- ListNode cur = this.head;
- if (cur == null) {
- System.out.println("当前链表为空!");
- return;
- }
- while (cur != null) {
- System.out.println(cur.val);
- cur = cur.next;
- }
- }
-
- public void printLast(){
- //逆序打印
- ListNode cur = this.last;
- if(cur == null){
- System.out.println("当前链表为空!");
- return;
- }
- while (cur != null) {
- System.out.println(cur.val);
- cur = cur.prev;
- }
- }
- public ListNode buyNode(int data) {
- // 申请新节点
- ListNode newnode = new ListNode(data);
- return newnode;
- }
链表为空就让链表的 head 和 last 都等于这个新节点
若链表不为空
原头节点的 prev 保存新插入节点的地址
新插入节点的 next 保存原头节点的地址
新插入节点成为新的头节点
- public void addFirst(int data) {
- //头插
- if (this.head == null) {
- this.head = buyNode(data);
- this.last = this.head;
- return;
- }
- ListNode newnode = buyNode(data);
- newnode.next = this.head;//新插入节点的 next 保存原头节点的地址
- this.head.prev = newnode;//原头节点的 prev 保存新插入节点的地址
- this.head = newnode;//新插入节点成为新的头节点
- }
测试
- public static void main(String[] args) {
- MyLinkedList linkedList = new MyLinkedList();
- linkedList.addFirst(1);
- linkedList.addFirst(2);
- linkedList.addFirst(3);
- linkedList.addFirst(4);
-
- linkedList.printHead();
- System.out.println("==============");
- linkedList.printLast();
- }
链表为空就让链表的 head 和 last 都等于这个新节点
若链表不为空
last.next 保存新插入节点的地址
新插入节点的 prev 保存 last 的地址
新插入节点成为 last
- public static void main(String[] args) {
- MyLinkedList linkedList = new MyLinkedList();
- linkedList.addLast(5);
- linkedList.addLast(6);
- linkedList.addLast(7);
- linkedList.addLast(8);
-
- linkedList.printHead();
- System.out.println("==============");
- linkedList.printLast();
- }
测试
- public static void main(String[] args) {
- MyLinkedList linkedList = new MyLinkedList();
- linkedList.addLast(5);
- linkedList.addLast(6);
- linkedList.addLast(7);
- linkedList.addLast(8);
-
- linkedList.printHead();
- System.out.println("==============");
- linkedList.printLast();
- }
- public int size() {
- //返回链表节点个数
- ListNode cur = this.head;
- int count = 0;
- while (cur != null) {
- count++;
- cur = cur.next;
- }
- return count;
- }
插入时需要检查坐标的合法性
合法区间是[0,size()]
指定位置合法后
新节点的 prev 存储原位置节点 prev 的地址
新节点的 next 存储原位置节点的地址
原位置的 prev 存储为新节点的地址
原位置前一节点的 next 存储为新节点的地址
为方便观察修改一下打印方法
- public void printHead() {
- //正序打印
- ListNode cur = this.head;
- if (cur == null) {
- System.out.println("当前链表为空!");
- return;
- }
- while (cur != null) {
- System.out.print(cur.val + " ");
- cur = cur.next;
- }
- }
-
- public void printLast() {
- //逆序打印
- ListNode cur = this.last;
- if (cur == null) {
- System.out.println("当前链表为空!");
- return;
- }
- while (cur != null) {
- System.out.print(cur.val + " ");
- cur = cur.prev;
- }
- }
测试
- public static void main(String[] args) {
- MyLinkedList linkedList = new MyLinkedList();
- linkedList.addLast(5);
- linkedList.addLast(6);
- linkedList.addLast(7);
- linkedList.addLast(8);
- linkedList.printHead();
- System.out.println();
- System.out.println("==========");
- linkedList.addAny(1, 99);
- linkedList.addAny(2, 199);
- linkedList.addAny(3, 299);
- linkedList.addAny(0, 122);
- linkedList.addAny(linkedList.size(), 999);
- linkedList.printHead();
-
- }
由于此处是基础数据类型
不需要对节点中存储的数据进行置空
如果存储的是引用数据类型就需要置空
将原头节点置空
头节点的下一个节点成为新的头节点
新的头节点的 prev 需要置空
- public void removeFirst() {
- //头删
- if (this.head == null) {
- System.out.println("当前链表为空!");
- return;
- }
- ListNode tmp = this.head.next;
- // this.head.val = null;//由于此处是基础数据类型 不需要对节点中存储的数据进行置空 如果存储的是引用数据类型就需要置空
- this.head = null;
- this.head = tmp;
- if(this.head == null){
- this.last = null;
- }else {
- this.head.prev = null;//新的头节点的 prev 需要置空
-
- }
- }
测试
- public static void main(String[] args) {
- MyLinkedList linkedList = new MyLinkedList();
- linkedList.addFirst(1);
- linkedList.addFirst(2);
- linkedList.addFirst(3);
- linkedList.addFirst(4);
-
- linkedList.printHead();
-
- linkedList.removeFirst();
- System.out.println();
- linkedList.printHead();
-
- linkedList.removeFirst();
- System.out.println();
- linkedList.printHead();
-
- linkedList.removeFirst();
- System.out.println();
- linkedList.printHead();
-
- linkedList.removeFirst();
- System.out.println();
- linkedList.printHead();
- }
由于此处是基础数据类型
不需要对节点中存储的数据进行置空
如果存储的是引用数据类型就需要置空
尾节点的前一个节点成为新的尾节点
新的尾节点的 next 需要置空
- public void removeLast() {
- //尾删
- if (this.last == null) {
- System.out.println("当前链表为空!");
- return;
- }
- // this.last.val = null;由于此处是基础数据类型 不需要对节点中存储的数据进行置空 如果存储的是引用数据类型就需要置空
- ListNode tmp = this.last.prev;
- this.last = null;
- this.last = tmp;
- if(this.last == null){
- this.head = null;
- }
- else {
- this.last.next = null;//新的尾节点的 next 需要置空
-
- }
- }
测试
- public static void main(String[] args) {
- MyLinkedList linkedList = new MyLinkedList();
- linkedList.addFirst(1);
- linkedList.addFirst(2);
- linkedList.addFirst(3);
- linkedList.addFirst(4);
-
- linkedList.printHead();
-
- linkedList.removeLast();
- System.out.println();
- linkedList.printHead();
-
- linkedList.removeLast();
- System.out.println();
- linkedList.printHead();
-
- linkedList.removeLast();
- System.out.println();
- linkedList.printHead();
-
- linkedList.removeLast();
- System.out.println();
- linkedList.printHead();
- }
删除时需要检查坐标的合法性
合法区间是[0,size())
将删除位置前节点的 next 保存为删除节点位置后节点的地址
将删除位置后节点的 prev 保存为删除节点位置前节点的地址
- public void removeAny(int index) {
- if (this.head == null) {
- System.out.println("当前链表为空!");
- return;
- }
- if (index < 0 && index >= this.size()) {
- throw new IndexillegalityException("下标不合法!");
- }
- if (index == 0) {
- removeFirst();
- return;
- } else if (index == size() - 1) {
- removeLast();
- return;
- }
- ListNode cur = this.head;
- while (index != 0) {
- //找要删除的节点
- cur = cur.next;
- index--;
- }
- cur.prev.next = cur.next;
- cur.next.prev = cur.prev;
- cur = null;
-
- }
测试
- public static void main(String[] args) {
- MyLinkedList linkedList = new MyLinkedList();
- linkedList.addFirst(1);
- linkedList.addFirst(2);
- linkedList.addFirst(3);
- linkedList.addFirst(4);
- linkedList.printHead();
- System.out.println();
-
- linkedList.removeAny(1);
- linkedList.printHead();
- System.out.println();
-
- linkedList.removeAny(1);
- linkedList.printHead();
- System.out.println();
-
- linkedList.removeAny(1);
- linkedList.printHead();
- System.out.println();
-
- linkedList.removeAny(1);
- linkedList.printHead();
- System.out.println();
- }
抛了一个空指针异常
说明在链表只剩下一个节点的时候需要特殊处理
- public void removeAny(int index) {
- if (this.head == null) {
- System.out.println("当前链表为空!");
- return;
- }
- if (index < 0 && index >= this.size()) {
- throw new IndexillegalityException("下标不合法!");
- }
- if (index == 0) {
- removeFirst();
- return;
- } else if (index == size() - 1) {
- removeLast();
- return;
- }
- ListNode cur = this.head;
- while (index != 0) {
- //找要删除的节点
- cur = cur.next;
- index--;
- }
- if(cur == null ){
- //判断是否只有一个节点
- //cur在移动后如果等于空,就说明一定只剩下一个节点
- this.last = null;
- this.head = null;
- }else {
- cur.prev.next = cur.next;
- cur.next.prev = cur.prev;
- cur = null;
- }
- }
将删除位置前节点的 next 保存为删除节点位置后节点的地址
将删除位置后节点的 prev 保存为删除节点位置前节点的地址
对头和尾做单独处理
- public void removeData(int data){
- //删除指定数据
- if (this.head == null) {
- System.out.println("当前链表为空!");
- return;
- }
- ListNode cur = this.head;
- while (cur != null){
- if(cur.val == data){
- if(cur == head){
- removeFirst();
- return;
- }else if(cur == last){
- removeLast();
- return;
- }else {
- cur.prev.next = cur.next;
- cur.next.prev = cur.prev;
- }
- }
- cur = cur.next;
- }
- System.out.println("当前链表中没有您要删除的数据");
- }
测试
- public static void main(String[] args) {
- MyLinkedList linkedList = new MyLinkedList();
- linkedList.addFirst(1);
- linkedList.addFirst(2);
- linkedList.addFirst(3);
- linkedList.addFirst(4);
- linkedList.printHead();
- System.out.println();
-
- linkedList.removeData(4);
- linkedList.printHead();
- System.out.println();
-
- linkedList.removeData(3);
- linkedList.printHead();
- System.out.println();
-
- linkedList.removeData(2);
- linkedList.printHead();
- System.out.println();
-
- linkedList.removeData(1);
- linkedList.printHead();
- }
将链表中所有节点值等于 data 的节点全部删除
将3.3.4 的方法中进行删除后继续遍历链表
遇到节点值为 data 的继续删除即可
- public void removeDataAll(int data){
- //删除所有节点值为data的节点
- if (this.head == null) {
- System.out.println("当前链表为空!");
- return;
- }
- boolean flg = false;
-
- ListNode cur = this.head;
- while (cur != null){
- if(cur.val == data){
- flg = true;
- if(cur == head){
- removeFirst();
- }else if(cur == last){
- removeLast();
- }else {
- cur.prev.next = cur.next;
- cur.next.prev = cur.prev;
- }
- }
- cur = cur.next;
- }
- if(!flg){
- System.out.println("当前链表中没有您要删除的数据!");
-
- }else {
- System.out.println("删除成功!");
- }
- }
测试
- public static void main(String[] args) {
- MyLinkedList linkedList = new MyLinkedList();
- linkedList.addFirst(4);
- linkedList.addFirst(4);
- linkedList.addFirst(4);
- linkedList.addFirst(4);
- linkedList.addFirst(2);
- linkedList.addFirst(1);
- linkedList.addFirst(5);
- linkedList.addFirst(6);
- linkedList.addFirst(4);
-
- linkedList.printHead();
- System.out.println();
-
- linkedList.removeDataAll(4);
- linkedList.printHead();
- System.out.println();
-
- }
即将所有节点全部删除
让每个节点的 next ,prev 都置空
- public void clear(){
- //删除整个链表
- if (this.head == null) {
- System.out.println("当前链表为空!");
- return;
- }
- ListNode cur = this.head;
- while (cur!= null){
- // cur.val = null;如果是引用数据类型就需要置空
- ListNode tmp = cur.next;
- cur.next = null;
- cur.prev = null;
- cur = tmp;
- }
- this.head = null;
- this.last = null;
- }
Java 中已经封装好了 LinkedList 类
LinkedList 官方文档 https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
- public static void main(String[] args) {
- LinkedList<Integer> linkedList = new LinkedList<>();
- LinkedList<Number> linkedList2 = new LinkedList<>();
-
- }
方法 | 功能 |
boolean
add
(E e)
|
尾插
e
|
void
add
(int index, E element)
将 e
插入到
index
位置
|
将
e
插入到
index
位置
|
boolean
addAll
(Collection<? extends E> c)
|
尾插
c
中的元素
|
E
remove
(int index)
|
删除
index
位置元素
|
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
的下标
|
List<E>
subList
(int fromIndex, int toIndex)
|
截取部分
list
|
…… | …… |
这里只说说 addAll 和 subList
- public static void main(String[] args) {
- LinkedList<Integer> linkedList = new LinkedList<>();
- linkedList.add(new Integer(2));
- linkedList.add(new Integer(3));
- linkedList.add(new Integer(4));
- linkedList.add(new Integer(5));
- System.out.println(linkedList);
-
- List<Integer> list2 = linkedList.subList(1,3);
- System.out.println(list2);
-
- linkedList.set(1,10);
- System.out.println(list2);
- }
与 ArrayList 实现的 subList
subList 只是将对应区间的地址截取出来返回
而不是产生新的对象返回
与 ArrayList 实现的 addAll 类似
形参 c 的类型必须是实现了 Collection 接口
且其中存放的数据必须是 E 本身或 E 的子类
- public static void main(String[] args) {
- LinkedList<Integer> linkedList = new LinkedList<>();
- linkedList.add(new Integer(2));
- linkedList.add(new Integer(3));
- linkedList.add(new Integer(4));
- linkedList.add(new Integer(5));
-
- LinkedList<Number> linkedList2 = new LinkedList<>(linkedList);
- System.out.println(linkedList);
- System.out.println(linkedList2);
-
- }
不同点 |
ArrayList
|
LinkedList
|
存储空间上
|
物理上一定连续
|
逻辑上连续,但物理上不一定连续
|
随机访问
|
支持
O(1)
|
不支持:
O(N)
|
头插
|
需要搬移元素,效率低
O(N)
|
只需修改引用的指向,时间复杂度为
O(1)
|
插入
|
空间不够时需要扩容
|
没有容量的概念
|
应用场景
|
元素高效存储
+
频繁访问
|
任意位置插入和删除频繁
|
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。