这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和
java
集合有个大概的了解。当然实现没有java
集合的实现那么复杂,功能也没有那么强大,但是可以通过这些简单的实现窥探到底层的一些共性原理。
一. 什么是单链表逆转?
我们知道,单链表的每个结点由两部分组成,一个数据域data
和一个指向其后继结点的指针域next
,最后一个结点的next
域为空。单链表逆转就是将链表中各结点的next
域指向它的前驱结点,原来第一个结点的next
域为空,头结点head
指向原来的最后一个节点。
单链表的逆转步骤描述如下:
1. 初始,设置p
结点指向第一个结点,front
结点指向p
的前驱结点,q
结点指向p
的后继结点。
2. 循环中,将p
的后继结点p.netx
指向p
的前驱结点front
3. 循环结束后已经实现逆转的单链表如下所示:
二. 算法实现
可逆转的单链表类是在前面文章已经实现的单链表SinglyLinkedList类的基础上增加了单链表逆转的功能,继承自SinglyLinkedList
类。可逆转的单链表类ReverseSinglyLinkedList
代码实现如下:
package org.light4j.dataStructure.linearList.linkList.reverse;
import org.light4j.dataStructure.linearList.linkList.Node;
import org.light4j.dataStructure.linearList.linkList.SinglyLinkedList;
/**
* 可逆转的单链表,继承自SinglyLinkedList
*
* @author longjiazuo
*/
public class ReverseSinglyLinkedList<E> extends SinglyLinkedList<E> {
public ReverseSinglyLinkedList() {
super();// 调用父类同参数的构造方法
}
/**
* 实现单链表逆转的方法
*/
public void reverse() {
Node<E> p = this.head;
Node<E> front = null;
Node<E> q = null;
while (p != null) {
q = p.next;// 设置q结点是p的后继结点
p.next = front;// 使p的后继结点指向其前驱节点
front = p;// front结点向后移动
p = q;// p结点向后移动
}
this.head = front;// 头结点指向front
}
}
代码解释:
① 设
p
指向单链表的某个结点,front
是p
的前驱结点,那么使p
的后继结点p.next
指向p
的前驱结点的语句是:p.next=front
,但是如果将p
的后继结点指向p
的前驱结点,那么p
和原来的后继结点之间的链接就断开了,于是我们需要声明一个q
节点来记住p
和原来后继结点之间的关系,使q=p.next
。front
,p
,q
这三个结点的引用同时沿着单链表向后移动。
三.测试
测试代码如下所示:
package org.light4j.dataStructure.linearList.linkList.reverse;
public class Test {
/**
* 测试
*
* @param args
*/
public static void main(String[] args) {
ReverseSinglyLinkedList<Integer> rslk = new ReverseSinglyLinkedList<Integer>();
for (int i = 1; i < 10; i++) {
rslk.add(0, new Integer(i));
}
System.out.println("单链表: " + rslk.toString());
rslk.reverse();
System.out.println("逆转后的单链表: " + rslk.toString());
}
}
运行结果如下所示:
四.源代码示例
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » 自己实现集合框架(四):可逆转单链表的实现