java模拟实现双向链表(双向链表 java)

网友投稿 324 2022-07-28


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

下图是双向链表的逻辑结构图,和单链表不同的是,双向链表中每个节点包含两个节点的指针引用,和一个数据域,这两个节点分别指向前一个节点和后一个节点;

双向链表的这种结构比起单链表,其改进之处正在于此,通过对前后节点的引用可以使得在整个链表中,通过给定的值,可以从前或者向后遍历,大大提升了遍历查询的效率,一定程度上解决了单链表的性能问题,但与此同时,链表的存储开销也增大了,我们熟悉的linkedList,其底层就是这个原理实现的.

废话不多说,相信通过上面的解释大家已经很明白了,下面直接上代码,可以结合代码和图结构理解双向链表,

public class DoubleLinkTest {

/**

* 内部构造节点类

*

* @param

*/

private class Node {

private T data;

private Node next; // 指向下一http://个节点的引用

private Node prev; // 指向前一个节点的引用

public Node(T data) {

this.data = data;

}

}

private Node head; // 模拟头结点

private Node last; // 模拟尾部节点

private Node other; // 暂定一个临时节点,用作指针节点

private int length;

public void DoubleLinkTest() {

head = new Node(null);

last = head;

length = 0;

}

public void DoubleLinkTest(T data) WTrxm{

head = new Node(data);

last = head;

length = 0;

}

/**

* 链表是否为空

*

* @return

*/

public boolean isEmpty() {

return length == 0;

}

/**

* 普通添加,往链表尾部添加

*

* @param data

*/

public void add(T data) {

if (isEmpty()) { // 链表为空,新创建一个链表

head = new Node(data);

last = head;

length++;

} else {

other = new Node(data);

other.prev = last;

last.next = other; // 将新的节点与原来的尾部节点进行结构上的关联

last = other; // other将成为最后一个节点

length++;

}

}

/**

* 在指定的数据后面添加数据

*

* @param data

* @param insertData

*/

public void addAfter(T data, T insertData) {

other = head;

while (other != null) { // 我们假定这个head是不为空的。

if (other.data.equals(data)) {

Node t = new Node(insertData);

t.prev = other;

t.next = other.next;// 对新插入的数据进行一个指向的定义

other.next = t;

if (t.next == null) {

last = t;

}

length++;

}

other = other.next;

}

}

/**

* 删除,删除指定的数据

*

* @param data

*/

public void remove(T data) {

other = head;// 我们假定这个head是不为空的。

while (other != null) {

if (other.data.equals(data)) {

other.prev.next = other.next;

length--;

}

other = other.next;

}

}

/**

* 测试打印数据

*/

public void printList() {

other = head;

for (int i = 0; i < length; i++) {

System.out.println(other.data + " ");

other = other.nexWTrxmt;

}

}

public static void main(String[] args) {

DoubleLinkTest link = new DoubleLinkTest();

link.add(1);

link.add(2);

link.add(3);

link.add(5);

link.add(6);

link.add(7);

link.printList();

System.out.println(" ============== ");

System.out.println(" ==== 在3后面添加一个数据开始========== ");

link.addAfter(3, 99);

link.printList();

System.out.println(" ==== 在3后面添加一个数据结束========== " + "\r\n");

System.out.println(" ==== 移除一个数据开始========== ");

link.remove(99);

link.printList();

System.out.println(" \r\n");

}

}

运行main函数,可以看到控制台的打印输出:


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Java实现线程通信的案例讲解(java线程间通信)
下一篇:Java利用栈实现简易计算器功能(栈有哪些常用运算)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~