但行好事  莫问前程

自己实现集合框架(四):可逆转单链表的实现

这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和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指向单链表的某个结点,frontp的前驱结点,那么使p的后继结点p.next指向p的前驱结点的语句是:p.next=front,但是如果将p的后继结点指向p的前驱结点,那么p和原来的后继结点之间的链接就断开了,于是我们需要声明一个q节点来记住p和原来后继结点之间的关系,使q=p.nextfrontpq这三个结点的引用同时沿着单链表向后移动。

三.测试

测试代码如下所示:

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());
    }
}

运行结果如下所示:

四.源代码示例

github地址:点击查看
码云地址:点击查看

打赏
欢迎关注人生设计师的微信公众账号
公众号ID:longjiazuoA

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

分享到:更多 ()

人生设计师-接受不同的声音

联系我关于我