Java实现双链表互相交换任意两个节点的方法示例

本文实例讲述了Java实现双链表互相交换任意两个节点的方法。分享给大家供大家参考,具体如下:

概述:

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

思路:

1、确定两个节点的先后顺序
2、next、prev互相交换顺序以及将换向前方的节点与之前的节点对接。(1.prev.next = 2)
3、判断是否相邻

实现代码:

链表类:

public class SLink {
  public SNode head;
  public SLink() {
    this.head = new SNode();
  }
  public boolean interChangeById(int id1,int id2) {
    SNode s = head;
    SNode node1 = null,node2 = null;
    int node1Count,node2Count;
    node1Count = node2Count = 0;
    if(id1 == id2) {
      return true;
    }
    /**
     * 向下遍历
     */
    while (s.next != null) {
      s = s.next;
      node1Count ++ ;
      if(s.student.stuId == id1) {
        /**
         * 记录节点1
         */
        node1 = s;
        break;
      }
    }
    s = head;
    while (s.next != null) {
      s = s.next;
      node2Count ++ ;
      if(s.student.stuId == id2) {
        /**
         * 记录节点2
         */
        node2 = s;
        break;
      }
    }
    if(node1 != null && node2 != null) {
      SNode temp = new SNode();
      /**
       * node1在后
       */
      if(node1Count > node2Count) {
        temp.next = node1.next;
        temp.prev = node1.prev;
        /**
         * 记录那个节点就先处理那个节点
         * 1、交换next
         * 2、交换prev
         * 3、设置之前节点的next(对接)
         */
        node1.next = node2.next;
        node1.prev = node2.prev;
        node2.prev.next = node1;
        if(node1.next.equals(node1)) {
          /**
           * 说明两个节点相邻
           */
          node1.next = node2;
          node2.next = temp.next;
          node2.prev = node1;
        }else {
          /**
           * 说明节点不相邻
           */
          node2.next = temp.next;
          node2.prev = temp.prev;
          temp.prev.next = node2;
        }
      }else {
        /**
         * node1在前
         */
        temp.next = node2.next;
        temp.prev = node2.prev;
        node2.next = node1.next;
        node2.prev = node1.prev;
        node1.prev.next = node2;
        if(node2.next.equals(node2)) {
          node2.next = node1;
          node1.next = temp.next;
          node1.prev = node2;
        }else {
          node1.next = temp.next;
          node1.prev = temp.prev;
          temp.prev.next = node1;
        }
      }
      return true;
    }
    return false;
  }
  public void displayStudent() {
    SNode s = head;
    while (s.next != null) {
      s = s.next;
      System.out.println(s.student);
    }
  }
}

节点类:

public class SNode {
  public Student student;
  public SNode next;
  public SNode prev;
  public SNode(Student student, SNode prev,SNode next) {
    this.student = student;
    this.next = next;
    this.prev = prev;
  }
  public SNode() {
    this.student = null;
    this.next = null;
    this.prev = null;
  }
}

Student类:

public class Student {
  public int stuId;
  public String name;
  public int age;
  public String className;
  public Student(int stuId, String name, int age, String className) {
    this.stuId = stuId;
    this.name = name;
    this.age = age;
    this.className = className;
  }
  public int getStuId() {
    return stuId;
  }
  public void setStuId(int stuId) {
    this.stuId = stuId;
  }
  public String getName() {
    return name;
  }
  public void setName(String name) {
    this.name = name;
  }
  public int getAge() {
    return age;
  }
  public void setAge(int age) {
    this.age = age;
  }
  public String getClassName() {
    return className;
  }
  public void setClassName(String className) {
    this.className = className;
  }
  @Override
  public String toString() {
    return "Student{" +
        "stuId=" + stuId +
        ", name='" + name + '\'' +
        ", age=" + age +
        ", className='" + className + '\'' +
        '}';
  }
}

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

(0)

相关推荐

  • java双向循环链表的实现代码

    例1: 复制代码 代码如下: package com.xlst.util; import java.util.HashMap;import java.util.Map;import java.util.UUID; /*** 双向循环链表* 完成时间:2012.9.28* 版本1.0* @author xlst**/public class BothwayLoopLinked {/*** 存放链表长度的 map* * 如果简单使用 static int 型的 size 基本类型变量,则只能维护一个

  • Java中双向链表详解及实例

    Java中双向链表详解及实例 写在前面: 双向链表是一种对称结构,它克服了单链表上指针单向性的缺点,其中每一个节点即可向前引用,也可向后引用,这样可以更方便的插入.删除数据元素. 由于双向链表需要同时维护两个方向的指针,因此添加节点.删除节点时指针维护成本更大:但双向链表具有两个方向的指针,因此可以向两个方向搜索节点,因此双向链表在搜索节点.删除指定索引处节点时具有较好的性能. Java语言实现双向链表: package com.ietree.basic.datastructure.dublin

  • java 实现双向链表实例详解

    java 实现双向链表实例详解 双向链表是一个基本的数据结构,在Java中LinkedList已经实现了这种结构,不过作为开发者,也要拥有自己显示这种结构的能力.话不多说,上代码:     首先是链表的节点类: /** * 链表节点 * @author Administrator * * @param <T> */ public class ChainNode<T> { private T data; //对象编号 private int dataNo; public ChainN

  • java中使用双向链表实现贪吃蛇程序源码分享

    使用双向链表实现贪吃蛇程序 1.链表节点定义: package snake; public class SnakeNode { private int x; private int y; private SnakeNode next; private SnakeNode ahead; public SnakeNode() { } public SnakeNode(int x, int y) { super(); this.x = x; this.y = y; } public int getX(

  • java实现单链表、双向链表

    本文实例为大家分享了java实现单链表.双向链表的相关代码,供大家参考,具体内容如下 java实现单链表: package code; class Node { Node next; int data; public Node(int data) { this.data=data; } } class LinkList { Node first; //头部 public LinkList() { this.first=null; } public void addNode(Node no) {

  • java基于双向环形链表解决丢手帕问题的方法示例

    本文实例讲述了java基于双向环形链表解决丢手帕问题的方法.分享给大家供大家参考,具体如下: 问题:设编号为1.2--n的几个小孩围坐一圈,约定编号为k(1=<k<=n)的小孩从1开始报数,数到m的那个出列,他的下一位又从1开始报数,数到m的那个人又出列,直到所有人出列为止,由此产生一个出队编号的序列. 我们现在用一个双向环形链表来解这一问题.先来看看下面这幅图: 圆圈代表一个结点,红色的指针指向下一个元素,紫色的指针指向上一个元素.first指针指向第一个元素,表明第一个元素的位置,curs

  • Java语言中链表和双向链表

    链表是一种重要的数据结构,在程序设计中占有很重要的地位.C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java语言比C和C++更容易实现链表结构.Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点. class Node { Object data; Node next;//指向下一个结点 } 将数据域定义成Object类是因为

  • java数据结构之实现双向链表的示例

    复制代码 代码如下: /** * 双向链表的实现 * @author Skip * @version 1.0 */public class DoubleNodeList<T> { //节点类 private static class Node<T>{  Node<T> perv;  //前节点  Node<T> next;  //后节点  T data;    //数据 public Node(T t){   this.data = t;  } } priv

  • Java模拟单链表和双端链表数据结构的实例讲解

    模拟单链表 线性表: 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构. 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的. 线性表的逻辑结构简单,便于实现和操作. 在实际应用中,线性表都是以栈.队列.字符串等特殊线性表的形式来使用的. 线性结构的基本特征为: 1.集合中必存在唯一的一个"第一元素": 2.集合中必存在唯一的一个 "最后元素" : 3.除最后一个元素之外,均有 唯一的后继(后件):

  • 详解java数据结构与算法之双链表设计与实现

    在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

随机推荐