前言
本篇主要介绍数据结构中的链表结构，单链表和双向的基本概念以及一些操作原理，和两种链表的一些合作操作，主要想通过本篇让大家对链表结构有一个更为具体的印象。
一、数据结构
数据结构：就是在计算机的缓存、内存、硬盘中如何组织管理数据的。重点在结构。
数据结构分为逻辑结构和物理机构
逻辑结构:思想上的结构，线性表（数组、链表），图，树，栈，队列
物理结构:真实存在的结构，紧密结构（顺序结构），跳转结构（链式结构）。
紧密结构（顺序结构）:数组为例，优点：寻址快—>查找元素块；缺点：删除和增加元素效率低
跳转结构:以链表（单向、双向、循环链表）为例，优点：删除和插入元素效率高，查询元素效率低
二、跳转结构(链表)
链表是以节点的方式来存储数据，是链式存储，每个节点包括data数据区和指针区。
单链表:单链表的包括data数据区来存储数据值value和下一个节点的next指针区域，指向下一个节点，最后一个节点的next指针区域指向null。
双链表:双链表的包括data数据区来存储数据值value、指向前一个节点的pre指针区域、指向下一个节点的next指针区域，指向下一个节点，最后一个节点的next指针区域指向null，指向前一个节点，第一个节点的pre指针区域指向null。
三、单链表的反转(逆序)
单链表的逆序逻辑，定义一个node节点，包括data数据区和指针区域，在反转逻辑中利用前向指针pre和后向指针next实现单链表的逆序逻辑，并且返回对应的head节点。
逆序之后的头部head返回，基于此继续执行逆序方法，直到heap为null。
逻辑：
先记录head.next赋值给next(next=head.next),反向之后head.next指向前一位应该是pre(head.next=pre)，head的位置给到pre(pre=head)，因为head需要标记下一位为头head(head=next)。
package com.czing.study.algorithm.linktable;
/**
* @Description
* 链表的操作
* 单链表的逆序操作代码演示
* @Author wangchengzhi
* @Date 2023/3/20 14:43
*/
public class ReverseLinkedList {
public static void main(String[] args) {
Node n1 = new Node(1);
n1.next=new Node(2);
n1.next.next=new Node(3);
n1= reverseLinkedList(n1);
while(n1!=null){
System.out.print(n1.value+" ");
n1=n1.next;
}
}
//定义node节点
public static class Node{
public int value;//节点的数据区
public Node next;//数据的指针区
public Node(int data){
value=data;
}
}
/**
* @Author wangchengzhi
* @Description 逆序实现逻辑
* @Date 15:07 2023/3/20
* @Param
* @return
**/
public static Node reverseLinkedList(Node head){
Node pre =null;
Node next =null;
//循环到节点为空的时候 说明是最后一个节点
while(head!=null){
//下一个节点next赋值为head.next
next= head.next;
head.next=pre;
pre=head;
head=next;
}
//交换处理之后，pre就是目前head的位置
return pre;
}
}
四、双链表的反转(逆序)
双链表的逆序逻辑，定义一个doubleNode节点，包括data数据区和指针区域(向后的指针next,向前的指针last)，在反转逻辑中利用前向指针pre和后向指针next实现双链表的逆序逻辑，并且返回对应的head节点。
逆序之后的头部head返回，基于此继续执行逆序方法，直到heap为null。
逻辑：
先记录head.next赋值给next(next=head.next)为了记录下一步的环境节点,反向之后head.next指向前一位应该是pre(head.next=pre)，head的向后的指针指向前一位(head.last=next)，head的位置给到pre(pre=head)，因为head需要标记下一位为头head(head=next)。
package com.czing.study.algorithm.linktable;
/**
* @Author wangchengzhi
* @Description
* 双向链表的反转逻辑处理
* 1、定义双链表节点DoubleNode,包含属性value、pre、next(比单链表多了pre指针)
*
* 2、定义反转的方案reverseList
* 先记录head.next赋值给next(next=head.next)为了记录下一步的环境节点,
* 反向之后head.next指向前一位应该是pre(head.next=pre)，
* head的向后的指针指向前一位(head.last=next)，
* head的位置给到pre(pre=head)，因为head需要标记下一位为头head(head=next)。
*
* 3、主方法里面创建4个节点，分别指明前后的指针
*
* 4、定义方法printDoubleLinkedList打印反转之后的节点状态
* @Date 16:42 2023/3/22
* @Param
* @return
**/
public class DoubleLinkedList {
public static class DoubleNode {
public int value;
//前驱
public DoubleNode pre;
//后继
public DoubleNode next;
public DoubleNode(int data) {
this.value = data;
}
}
//双向链表反转
public static DoubleNode reverseList(DoubleNode head) {
//记录原前驱
DoubleNode pre = null;
//记录原后继的变量
DoubleNode next;
while (head != null){
//记录原后继
next = head.next;
//反转<-变为->
head.next = pre;
//反转->变为<-
head.pre = next;
//刷新前驱
pre = head;
//刷新当前节点
head = next;
}
//运行到最后pre是新的头
return pre;
}
public static void printDoubleLinkedList(DoubleNode head) {
System.out.print("Double Linked List: ");
DoubleNode end = null;
//从前向后打印节点1，2，3，4
while (head != null) {
System.out.print(head.value + " ");
end = head;
head = head.next;
}
System.out.print("| ");
//从后向前打印节点4，3，2，1
while (end != null) {
System.out.print(end.value + " ");
end = end.pre;
}
System.out.println();
}
public static void main(String[] args) {
//定义节点数据为1
DoubleNode head2 = new DoubleNode(1);
//节点1的下一个节点为2
head2.next = new DoubleNode(2);
//下一个节点2的前一个节点为1
head2.next.pre = head2;
//节点1的下一个节点2的下一个节点为3
head2.next.next = new DoubleNode(3);
//节点1的下一个节点2的下一个节点3的前一个节点为节点2
head2.next.next.pre = head2.next;
//节点1的下一个节点2的下一个节点3的下一个节点为4
head2.next.next.next = new DoubleNode(4);
//节点1的下一个节点2的下一个节点3的下一个节点4的前一个节点为节点3
head2.next.next.next.pre = head2.next.next;
//打印原始的节点从前到后 | 从后到前
printDoubleLinkedList(head2);
//打印反转之后的节点 从前到后 | 从后到前
printDoubleLinkedList(reverseList(head2));
}
}
结语:
本篇主要介绍了，单链表和双链表的概念，以及单链表和双链表的反转逆序逻辑，双链表相比于单链表多了一个前向指针的概念。在做双链表逆序的时候要考虑前向指针pre的处理。