双向链表
双向链表的定义
双向链表也叫双链表，与单向链表不同的是，每一个节点有三个区域组成：两个指针域，一个数据域
- 前一个指针域：存储前驱节点的内存地址
- 后一个指针域：存储后继节点的内存地址
- 数据域：存储节点数据
以下就是双向链表的最基本单位
节点的前指针域指向前驱，后指针域执行后继
完整的双向链表
双向链表的功能
-
增
-
向双向链表的尾节点之后添加节点
-
尾节点的后指针域存储新添加节点的内存地址
-
新添加节点的前指针域存储尾节点的内存地址
注意：此时尾节点就是新添加的这个节点
-
-
向双向链表的首元节点之前添加节点
-
新添加节点的后指针域存储首元节点的内存地址
-
首元节点的前指针域存储新添加节点的内存地址
注意：此时首元节点就是新添加的这个节点
-
-
-
删
-
删除中间节点时修改改节点的前驱和后继的指针方向即可
注意：被删除的节点称之为：野节点，这并不是真正意义上的删除，它在内存中依旧存在。那么野节点的最终归宿是被JVM的GC（垃圾回收器）所回收，也就是释放该节点的内存空间，这才是真正意义上的删除
额外知识：java中的垃圾回收器（Garbage Collector，GC）负责管理内存的分配和释放。当一个对象没有任何引用指向它时，它就变得不可达，而垃圾回收器会将其标记为垃圾对象，并在适当的时候回收该对象所占用的内存空间。这个过程称为垃圾回收。
-
-
改
- 挪动指针找到要修改的节点，之后讲修改节点的数据域中的数据修改掉
-
查
- 挪动指针找到要所要查找的数据。
特点
- 双向性：
- 每个节点除了存储自己的数据外，还包含两个指针域，分别存储前驱和后继的内存地址，因此可以在链表中向前或向后遍历。
- 动态性：
- 双向链表可以在运行时动态地添加、删除和修改节点，相对于数组等静态数据结构更加灵活。
- 插入和删除操作高效：
- 由于双向链表中的节点包含指向前驱和后继的的指针，因此插入和删除操作只需要调整节点前后的指针，而不需要像数组那样移动大量元素。
- 空间利用率较高：
- 相比单向链表，双向链表需要额外的指针来表示前一个节点，空间利用率略低一些，但在某些情况下方便了一些操作。
- 双向遍历能力：
- 双向链表可以从任意节点开始向前或向后遍历，这在某些场景中非常有用，例如需要反向迭代链表。
双向链表在内存开销上相对于单向链表稍高。
由于有两个指针，插入和删除操作涉及到更多的指针修改，相对于单向链表略微复杂。
单向链表和双向链表的区别
单向链表相对于双向链表更简单且节省内存，适用于对内存占用敏感且只需要单向遍历的情况。
而双向链表由于具有双向遍历的能力，适用于需要频繁插入、删除和反向遍历的场景。文章来源：https://www.toymoban.com/news/detail-767431.html
在选择使用哪种链表结构时，应根据具体需求权衡其优缺点。文章来源地址https://www.toymoban.com/news/detail-767431.html
MyList
public interface MyList<E> {
//添加节点数据
void add(E element);
//获取节点数据
E get (int index);
//获取链表长度
int size();
//根据指针移除节点
E remove(int index);
//从头添加元素
void addFirst(E element);
//从尾添加元素
void addLast(E element);
}
MyDoubleLinkedList
public class MyDoubleLinkedList<E> implements MyList<E> {
private int size;//记录元素的个数
private Node head ;// 记录头节点
private Node tail;//记录尾节点
/**
* 向双向链表中添加元素数据
* @param element
*/
@Override
public void add(E element) {
this.linkLast(element);
}
/**
* 将节点对象添加到双向链表的尾部
* @param element
*/
private void linkLast(E element){
//获取尾节点
Node t = this.tail;
Node<E> node = new Node<>(t,element,null);
//将新节点定义为尾节点
this.tail = node;
if (t == null){//当t等于空的时候说明这个链表是个空链表
this.head=node;//将向的元素数据赋值到头节点
}else{
t.next=node;//否则将新元素赋值到尾节点之后
}
this.size++;//添加成功长度自增加一
}
/**
* 根据指针获取对应的元素数据
* @param index
* @return
*/
@Override
public E get(int index) {
//对index做合法性校验
this.rangeCheck(index);
Node<E> node = this.getNode(index);
return node.item;
}
/**
* 判断当前index的合法性
*/
private void rangeCheck(int index){
if(!(index >=0 && index < this.size)){
int a = this.size-1;
throw new IndexOutOfBoundsException("您输入的索引为："+index+"它的指针长度为："+a);
}
}
/**
* 根据位置获取指定的节点对象
* @param index
* @return
*/
private Node getNode(int index){
//判断当前输入的指针距离头或者尾哪个节点近
//如果输入的指针大，从尾部开始找，
//如果输入的指针小，从头部开始找
if (index < (this.size >> 1)){
Node node = this.head;
//遍历指针
for(int i =0; i < index;i++){
//拿到指针处的下一个节点对象赋值node
node=node.next;
}
return node;
}else {
Node node = this.tail;
//从尾节点找指针
for (int i = this.size-1; i>index; i--){
node = node.prev;
}
return node;
}
}
/**
* 获取元素的长度（个数）
* @return
*/
@Override
public int size() {
return this.size;
}
/**
* 根据指定指针删除元素
* @param index
* @return
*/
@Override
public E remove(int index) {
//对index指针进行合法性校验
this.rangeCheck(index);
//根据index进行获取节点对象，判断从头删还是从尾部删除
Node<E> node = this.getNode(index);
//获取index指针处的节点元素数据
E item = node.item;
//判断当前节点是否尾头节点
if (node.prev == null){
this.head = node.next;
}else {
//完成当前节点的直接前驱节点和当前节点的直接后继节点，挂接
node.prev.next = node.next;
}
//当前节点断掉与它直接前驱点的连接
node.prev = null;
//当前节点断掉与他直接后继节点的连接
node.next =null;
node.item =null;
//长度自减一
this.size--;
//返回被删除的节点元素数据
return item;
}
//从头开始添加元素
@Override
public void addFirst(E element) {
this.linkFirst(element);
}
//从尾部添加元素
@Override
public void addLast(E element) {
this.linkLast(element);
}
//在链表的头添加元素
private void linkFirst(E element){
//获取头节点对象
Node head = this.head;
Node node = new Node(null,element,head);
//将新节点定义为头节点
this.head = node;
//判断当前链表中是否有节点，如果没有该节则是头节点也是尾节点
if(this.head == null){
this.tail = node;
}else {
this.head.prev = node;
}
this.size++;//记录链表长度
}
/**
* 创建节点类
* @param <E>
*/
class Node<E> {
private E item;//记录元素
private Node<E> next; // 下一个节点对象
private Node<E> prev; // 上一个节点对象
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
测试
public class MyLinkedMain {
public static void main(String[] args) {
MyDoubleLinkedList linkedList = new MyDoubleLinkedList();
linkedList.add(12);
linkedList.add(13);
linkedList.add(14);
linkedList.add(15);
linkedList.add(16);
System.out.println(linkedList.get(3));//3是指针，从尾部开始找
System.out.println(linkedList.get(4));//4是指针，从尾部开始找
System.out.println(linkedList.get(1));//1是指针，从头部开始找
System.out.println(linkedList.size());//获取linkedList长度
System.out.println("删除前的指针1处的数据"+linkedList.get(1));
System.out.println(linkedList.remove(1));
System.out.println("删除后的指针1处的数据"+linkedList.get(1));
System.out.println("删除前的指针0处的数据"+linkedList.get(4));
System.out.println(linkedList.remove(4));
try {
System.out.println("删除后的指针0处的数据"+linkedList.get(4));
}catch (Exception e) {
e.printStackTrace();
}finally {
System.out.println("删除后的链表长度"+linkedList.size());//获取linkedList长度
}
}
}
到了这里，关于数据结构-链表结构-双向链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
