双向链表结构详解
- 2022-09-15 09:45:46
- 882次 极悦
双向链表的节点比单链表的节点多一个pre域，也就是存放当前节点的前一个节点地址的地方。
单链表里有许多操作是要找到待操作节点的前一个节点的，而双向链表则不需要，因为双向链表可以得到当前节点的前一个和后一个节点信息，可以完成相应的操作。
双向链表节点：
节点类：
class Node{
//pre表示前一个节点，next表示后一个节点
//no表示序号，其他为一些数据
private Node pre;
private Node next;
private int no;
private String name;
private String nickname;
public Node(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
//get set 方法省略
}
双向链表类(带头节点)：
双向链表的基本操作后面追加
class TwoWayLinkedList{
private Node head = new Node(0,"","");
//无参构造函数
public TwoWayLinkedList(){
}
public void setHead(Node node){
this.head = node;
}
public Node getHead(){
return this.head;
}
}
接下来就是给双向链表类添加一些基本方法了，插入这里提供按序号插入法，其他插入类似，然后就是删除，修改，遍历方法了。
添加节点方法(按序号插入)，该方法在双向链表类内部
思路：
插入节点的插入位置在cur指针的前面时
1.插入时先设置待插入节点的node的pre域，即把cur的pre域设置为node的pre域
2.再把cur的pre域对应节点的next域设为node
3.然后将cur的的pre域设为node，node的next域设为cur 即：
node.setPre(cur.getPre());
node.setNext(cur);
cur.getPre().setNext(node);
cur.setPre(node);
插入节点的插入位置在cur指针后面时又分为：在链表尾部插入和在链表头部插入(即链表为空时插入第一个节点)
特别注意：插入第一个节点时和在链表尾部插入时，cur很容易出现空指针异常，所以要分三种插入的情况
参数：节点(Node)
返回值：无
public void add(Node node){
//先判断链表是否为空，为空说明这是插入的第一个节点
//第一个节点插入因为head的next域为空
//head.getNext().getPre()会报空指针异常错误
//所以给第一个节点设置pre域时要直接指向head
if(head.getNext()==null){
node.setNext(head.getNext());
node.setPre(head);
head.setNext(node);
return;
}
//代码走到这里说明双向链表至少有一个节点
//创建一个cur指针，指向链表的第一个节点
Node cur = head.getNext();
//如果cur指向最后一个节点还没有比待插入节点序号大的
//就插入到链表最后
while(true){
//如果cur当前指向的节点序号大于待插入节点的序号
//说明待插入节点应该插在cur当前指向节点的前一个位置
//插入之后就退出循环，插入方法也就执行完了
if(cur.getNo()>node.getNo()){
node.setPre(cur.getPre());
node.setNext(cur);
cur.getPre().setNext(node);
cur.setPre(node);
break;
}else if(cur.getNo()==node.getNo()){
//编号存在就不插入，退出循环
System.out.printf("编号%d已存在\n",node.getNo());
break;
}else if(cur.getNext()==null){
//判断当前cur指向的是不是最后一个节点
//如果是，就插入到链表最后
//进入这个if分支
//说明待插入节点序号比前面节点序号都大
//而且待插入节点序号不存在于链表中
node.setPre(cur);
cur.setNext(node);
//节点初始化时，其pre与next默认指向null
//所以不需要让node的next域再设置为null
//或者设为cur的next域
break;
}
//如果上面的if分支一个都没进入
//说明cur指向的节点不满足，让cur指向下一个节点
cur = cur.getNext();
}
}
插入方法写好之后就可以写遍历方法，将双向链表进行打印输出，该方法还是在双向链表类内部
参数：无
返回值：无
public void print(){
//先判断链表是否为空
if(head.getNext()==null){
System.out.println("双向链表为空");
return;
}
//定义一个cur指针指向链表的头节点，然后遍历链表
Node cur = head;
//开始遍历
while(true){
//cur指向链表最后一个节点就退出循环
if(cur.getNext()==null){
break;
}
//因为cur初始化是head
//所以打印cur指向的下一个节点
//打印时需要打印当前节点和前一个节点
//避免插入时节点pre域出现问题
System.out.println("now:"+cur.getNext()+
"pre:"+cur.getNext().getPre());
//然后让cur指向下一个节点
cur = cur.getNext();
}
}
链表删除思路：
1.先遍历通过cur找到待删除节点
此时cur指向的就是待删除节点，让待删除节点的前一个节点的next域直接跨过待删除节点指向待删除节点的next域。
2.让待删除节点的下一个节点的pre域直接跨过待删除节点指向待删除节点的pre域
cur.getPre().setNext(cur.getNext());
cur.getNext().setPre(cur.getPre());
特别注意：如果待删除节点是链表最后一个，那么cur.getNext()就为空，2)的操作就会出现空指针异常，这里需要判断一下
参数：待删除节点的序号(int)
返回值：无
该方法仍然在双向链表内部
public void remove(int no){
//先判断链表是否为空
if(head.getNext()==null){
System.out.println("链表为空");
return;
}
//创建一个cur指针来遍历链表，初始化指向链表第一个节点
Node cur = head.getNext();
while(true){
if(cur.getNo()==no){//找到待删除节点
cur.getPre().setNext(cur.getNext());
if(cur.getNext()!=null){
//如果待删除节点为链表最后一个节点
//不执行下面语句
cur.getNext().setPre(cur.getPre());
}
break;
}else if(cur.getNext()==null){
//当前cur指向的是链表最后一个节点
//说明没有传来的序号匹配不到待删除节点
System.out.println("没有该编号:"+no+"节点");
break;
}
//未执行上面代码，让cur后移
cur = cur.getNext();
}
}
链表修改节点信息思路：
修改节点信息与删除节点类似，遍历找到待更新节点，然后替换信息，未找到就在控制台输出提醒，不可修改节点序号
参数：一个节点(node)
返回值：无
public void update(Node node){
//先判断链表是否为空
if(head.getNext()==null){
System.out.println("链表为空");
return;
}
//创建一个cur指针来遍历链表，初始化指向链表第一个节点
Node cur = head.getNext();
while(true){
if(cur.getNo()==node.getNo()){//找到待修改节点
//修改节点信息
cur.setName(node.getName());
cur.setNickname(node.getNickname());
break;
}else if(cur.getNext()==null){
//当前cur指向的是链表最后一个节点
//说明传来节点的序号匹配不到
System.out.println("没有该编号:"
+node.getNo()+"节点");
break;
}
//未执行上面代码，让cur后移
cur = cur.getNext();
}
}
之前单链表的操作，如：单链表长度，获取倒数第k个节点，单链表反转，单链表反向输出，合并两个有序单链表为一个单链表且仍然有序。
双向链表的操作，下面直接给出代码，思路是和单链表的类似，就是设置节点pre域麻烦一点。
双向链表全部代码如下：
package com.sixteen.linkedlist;
public class TwoWayLinkedListDemo {
public static void main(String[] args) {
TwoWayLinkedList twoWayLinkedList = new TwoWayLinkedList();
twoWayLinkedList.add(new Node(1,"宋江","及时雨"));
twoWayLinkedList.add(new Node(3,"吴用","智多星"));
twoWayLinkedList.add(new Node(2,"卢俊义","玉麒麟"));
twoWayLinkedList.add(new Node(4,"林冲","豹子头"));
System.out.println("原双向链表-----");
twoWayLinkedList.print();
/*System.out.println(getSize(twoWayLinkedList.getHead()));
twoWayLinkedList.update(new Node(2,"卢俊义222","玉麒麟222"));
System.out.println("修改后的双向链表-----");
twoWayLinkedList.print();*/
/*System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 1));
System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 4));
System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 2));
System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 6));*/
/*twoWayLinkedList.remove(3);
System.out.println("-----");
twoWayLinkedList.print();*/
/*//reversePrint(twoWayLinkedList.getHead());
reverse(twoWayLinkedList.getHead());
System.out.println("反转后的双向链表-----");
twoWayLinkedList.print();*/
/*TwoWayLinkedList twoWayLinkedList1 = new TwoWayLinkedList();
twoWayLinkedList1.add(new Node(1,"宋江","及时雨"));
twoWayLinkedList1.add(new Node(3,"吴用","智多星"));
twoWayLinkedList1.add(new Node(5,"卢俊义","玉麒麟"));
twoWayLinkedList1.add(new Node(7,"林冲","豹子头"));
TwoWayLinkedList twoWayLinkedList2 = new TwoWayLinkedList();
twoWayLinkedList2.add(new Node(2,"宋江2","及时雨2"));
twoWayLinkedList2.add(new Node(4,"吴用4","智多星4"));
twoWayLinkedList2.add(new Node(6,"卢俊义6","玉麒麟6"));
twoWayLinkedList2.add(new Node(8,"林冲8","豹子头8"));
TwoWayLinkedList twoWayLinkedList = mergeTwoTwoWayLinkedList(twoWayLinkedList1, twoWayLinkedList2);
twoWayLinkedList.print();*/
}
public static Node getTheLastIndexNode(Node head,int index){
if (head.getNext()==null){
return null;
}
int size = getSize(head);
if (index<0 || index>size){
return null;
}
Node temp = head.getNext();
for (int i = 0; i < size-index; i++) {
temp = temp.getNext();
}
return temp;
}
public static int getSize(Node head){
if (head.getNext()==null){
return 0;
}
int count = 0;
Node temp = head.getNext();
while (temp!=null){
count++;
temp = temp.getNext();
}
return count;
}
public static TwoWayLinkedList mergeTwoTwoWayLinkedList(TwoWayLinkedList twoWayLinkedList1, TwoWayLinkedList twoWayLinkedList2){
Node head1 = twoWayLinkedList1.getHead();
Node head2 = twoWayLinkedList2.getHead();
if (head1.getNext()==null || head2.getNext()==null){
return head1.getNext()==null ? twoWayLinkedList2:twoWayLinkedList1;
}
Node cur = head1.getNext();
Node node;
while (cur!=null){
node = cur;
cur = cur.getNext();
twoWayLinkedList2.add(node);
}
return twoWayLinkedList2;
}
public static void reverse(Node head){
//如果链表为空或链表只有一个元素，不做任何操作
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
if (head.getNext().getNext()==null){
return;
}
Node temp = head.getNext();
Node reverseNode = new Node(0,"","");
Node node;
while (temp!=null){
node = temp;
temp = temp.getNext();
if (reverseNode.getNext()==null){
node.setNext(reverseNode.getNext());
node.setPre(reverseNode);
reverseNode.setNext(node);
}else {
node.setNext(reverseNode.getNext());
node.setPre(reverseNode);
reverseNode.getNext().setPre(node);
reverseNode.setNext(node);
}
}
head.setNext(reverseNode.getNext());
}
public static void reversePrint(Node head){
//链表为空或者链表只有一个节点时，直接输出
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
if (head.getNext().getNext()==null){
System.out.println(head.getNext());
return;
}
Node temp = head.getNext();
//while循环结束之后temp定位到最后一个节点，然后再反向遍历链表
while (temp.getNext()!=null){
temp = temp.getNext();
}
while (temp.getPre()!=null){
System.out.println(temp);
temp = temp.getPre();
}
}
}
class TwoWayLinkedList{
private Node head = new Node(0,"","");
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
public void add(Node node){
if (head.getNext()==null){
node.setPre(head);
node.setNext(head.getNext());
head.setNext(node);
return;
}
Node cur = head.getNext();
while (true){
if (cur.getNo()>node.getNo()){
node.setPre(cur.getPre());
node.setNext(cur);
cur.getPre().setNext(node);
cur.setPre(node);
break;
}else if (cur.getNo()==node.getNo()){
System.out.printf("编号%d已存在\n",node.getNo());
break;
}else if (cur.getNext()==null){
node.setPre(cur);
cur.setNext(node);
break;
}
cur = cur.getNext();
}
}
public void remove(int no){
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
Node cur = head.getNext();
while (true){
if (cur.getNo()==no){
cur.getPre().setNext(cur.getNext());
if (cur.getNext()!=null){//如果当前cur指向的是链表最后一个节点，就不执行下面的操作
cur.getNext().setPre(cur.getPre());
}
if (cur.getNext()==null){//找到相应节点且这个节点是最后一个节点
cur.getPre().setNext(null);
}else {
cur.getPre().setNext(cur.getNext());
cur.getNext().setPre(cur.getPre());
}
break;
}else if (cur.getNext()==null){
System.out.println("没有编号"+no+"的节点");
break;
}
cur = cur.getNext();
}
}
public void update(Node node){
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
Node cur = head.getNext();
while (true){
if (cur.getNo()==node.getNo()){
cur.setName(node.getName());
cur.setNickname(node.getNickname());
break;
}else if (cur.getNext()==null){
System.out.println("没有编号"+node.getNo()+"节点");
break;
}
cur = cur.getNext();
}
}
public void print(){
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
Node cur = head;
while (true){
if (cur.getNext()==null){
break;
}
System.out.println("now:"+cur.getNext()+
"pre:"+cur.getNext().getPre());
cur = cur.getNext();
}
}
}
class Node{
private Node pre;
private Node next;
private int no;
private String name;
private String nickname;
public Node(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
public Node getPre() {
return pre;
}
public void setPre(Node pre) {
this.pre = pre;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getNickname() {
return nickname;
}
public void setNickname(String nickname) {
this.nickname = nickname;
}
}
选你想看
你适合学Java吗？4大专业测评方法
代码逻辑 吸收能力 技术学习能力 综合素质
先测评确定适合在学习
在线申请免费测试名额
价值1998元实验班免费学
价值1998元实验班免费学
在线咨询
免费试学