这个链表,以前上学的时候,学c语言,还是数据结构的时候,学过。也许也实现过吧。下面我就简单记录下这个链表的实现。

单向链表跟单向循环链表的差别就是:单向链表是有结束位的,指向null的时候,就到结尾了,但是单向循环链表,他就是一个圈,要是不设置指定位置,他是会一直转下去的,转着转着就会出现OOM异常了,也就是内存溢出啦。

单链表

先看单链表的节点对象--Node类。

这是组成链表的节点,就像一条铁链上的每个铁环一样,一环扣一环,那这个链就出来啦。

package com.lxk.linkedList.oneWay; 
 
/** 
 * Created by lxk on 2017/8/1 
 */ 
public class Node<K, V> { 
    private final K key; 
    private V value; 
    private Node<K, V> next; 
 
    public Node(K key, V value, Node<K, V> next) { 
        this.key = key; 
        this.value = value; 
        this.next = next; 
    } 
 
    public K getKey() { 
        return key; 
    } 
 
    public V getValue() { 
        return value; 
    } 
 
    public void setValue(V value) { 
        this.value = value; 
    } 
 
    public Node<K, V> getNext() { 
        return next; 
    } 
 
    public void setNext(Node<K, V> next) { 
        this.next = next; 
    } 
}

要是看过hashmap源码的哥们,这个类就很好理解啦,其实也简单,这个对象就三个属性,一个k,一个v,一个next指针。

可能有个高级点的地方,就是这个类使用了泛型。泛型说高级也不算高级。

可以简单理解为,我这个类型是根据传进来的类型设置的也可以。

想深入透彻了解这个泛型相关知识的,可以看以下2个链接。

Java泛型详解:和Class的使用。泛型类,泛型方法的详细使用实例

Java泛型: 中的? 和 extends 的理解和使用实例

以上2篇文章,虽然是转载的,但是,讲的却是极好的。


下面看对单链表的操作类--OneWayLinkedList类

package com.lxk.linkedList.oneWay; 
 
/** 
 * 单向链表 
 * <p> 
 * Created by lxk on 2017/8/1 
 */ 
public class OneWayLinkedList { 
 
    /** 
     * 获得单向链表(头插法生成的单向链表--后来的在链表头部) 
     */ 
    public static Node<Integer, Integer> getOneWayLinkedList() { 
        Node<Integer, Integer> temp = null; 
        for (int i = 1; i <= 6; i++) { 
            temp = new Node<>(i, i, temp);//头插法:先来的在链尾 
        } 
        return temp; 
    } 
 
    /** 
     * 获得单向链表(尾插法生成的单向链表--后来的链在链表尾部) 
     */ 
    public static Node<Integer, Integer> getOneWayLinkedListTail() { 
        Node<Integer, Integer> headWillMove = new Node<>(1, 1, null); 
        Node<Integer, Integer> headNoMove = headWillMove;//headWillMove,但是这个headNoMove是一直指向链表头的。返回他就对了。 
        for (int i = 2; i <= 6; i++) { 
            headWillMove.setNext(new Node<>(i, i, null));//尾插法:先来的在链头 
            headWillMove = headWillMove.getNext(); 
        } 
        return headNoMove; 
    } 
 
    /** 
     * 输出单向链表 
     */ 
    public static void forLinkedList(Node<Integer, Integer> linkedList) { 
        StringBuilder sb = new StringBuilder(); 
        sb.append("{"); 
        while (linkedList != null) { 
            sb.append("[k:").append(linkedList.getKey()).append(" v:").append(linkedList.getValue()).append("]"); 
            linkedList = linkedList.getNext(); 
        } 
        sb.append("}"); 
        System.out.println(sb.toString()); 
    } 
 
    /** 
     * 获得单向链表的最后一个节点 
     */ 
    public static Node<Integer, Integer> getLastNode(Node<Integer, Integer> linkedList) { 
        while (linkedList.getNext() != null) { 
            linkedList = linkedList.getNext(); 
        } 
        return linkedList; 
    } 
 
    /** 
     * 获得链表的长度 
     */ 
    public static int getOneWayLinkedListSize(Node<Integer, Integer> linkedList) { 
        int size = 0; 
        while (linkedList != null) { 
            size++; 
            linkedList = linkedList.getNext(); 
        } 
        return size; 
    } 
 
    /** 
     * 在链表指定位置之后插入元素 
     */ 
    public static void insertInLinkedList(int index, int key, int value, Node<Integer, Integer> linkedList) { 
        int size = getOneWayLinkedListSize(linkedList); 
        if (index < 0 || index >= size) { 
            System.out.println("out of index bounds"); 
            return; 
        } 
        for (int i = 0; i < size; i++) { 
            if (index == i) { 
                linkedList.setNext(new Node<>(key, value, linkedList.getNext())); 
                break; 
            } 
            linkedList = linkedList.getNext(); 
        } 
    } 
 
    /** 
     * 在链表指定位置之后删除节点 
     */ 
    public static void removeInLinkedList(int index, Node<Integer, Integer> linkedList) { 
        int size = getOneWayLinkedListSize(linkedList); 
        if (index < 0 || index >= size) { 
            System.out.println("out of index bounds"); 
            return; 
        } 
        for (int i = 0; i < size; i++) { 
            if (index == i) { 
                if (linkedList.getNext() == null) { 
                    System.out.println("out of index bounds"); 
                    break; 
                } 
                linkedList.setNext(linkedList.getNext().getNext()); 
                break; 
            } 
            linkedList = linkedList.getNext(); 
        } 
    } 
 
} 

这个 类的每个方法,都写了注释,也就是简单的对单向链表的一些简单操作。


单向循环链表

这个单向循环链表,就是在单向链表的基础上,把首尾给连起来,他就是循环链表了。

package com.lxk.linkedList.circularList; 
 
import com.lxk.linkedList.oneWay.Node; 
import com.lxk.linkedList.oneWay.OneWayLinkedList; 
 
/** 
 * 循环链表 
 * <p> 
 * Created by lxk on 2017/8/1 
 */ 
public class CircularOneWayList { 
 
    /** 
     * 获得单向循环链表 
     * 
     * @return 获得单向循环链表,默认返回的就链表头。 
     */ 
    public static Node<Integer, Integer> getCircularOneWayList() { 
        //获得的单向链表的头 
        Node<Integer, Integer> head = OneWayLinkedList.getOneWayLinkedListTail(); 
        //找到这个链表的尾 
        Node<Integer, Integer> tail = OneWayLinkedList.getLastNode(head); 
        //首尾相连,就成环了。 
        tail.setNext(head); 
        return head; 
    } 
 
    /** 
     * 获得循环链表的长度(要想获得长度,得设置个停止标记。) 
     * 
     * @param linkedList 单向循环链表,(必须是)链表头的位置开始。 
     */ 
    public static int getCircularLinkedListSize(Node<Integer, Integer> linkedList) { 
        //注意:前提条件-->假设所有的值不重复,才能这么干。 
        int size = 1;//默认从1开始,循环到1时结束, 
        linkedList = linkedList.getNext();//跨过key为1的节点,也就是把key为1的节点,作为标记。 
        while (linkedList.getKey() != 1) { 
            size++; 
            linkedList = linkedList.getNext(); 
        } 
        return size; 
    } 
 
} 



最后,看主测试代码

package com.lxk.linkedList; 
 
import com.lxk.linkedList.oneWay.Node; 
 
import static com.lxk.linkedList.circularList.CircularOneWayList.*; 
import static com.lxk.linkedList.oneWay.OneWayLinkedList.*; 
 
/** 
 * 链表测试 
 * <p> 
 * Created by lxk on 2017/8/1 
 */ 
public class Main { 
    public static void main(String[] args) { 
        testOneWayLinkedList();//单向链表 
        testCircularOneWayList();//循环链表 
    } 
 
    /** 
     * 测试循环链表 
     */ 
    private static void testCircularOneWayList() { 
        Node<Integer, Integer> linkedList = getCircularOneWayList();//获得初始化链表 
        //forLinkedList(linkedList);//打印 
        System.out.println(getCircularLinkedListSize(linkedList)); 
    } 
 
    /** 
     * 测试单向链表 
     */ 
    private static void testOneWayLinkedList() { 
        Node<Integer, Integer> linkedList = getOneWayLinkedList();//获得初始化链表---头插法 
        //Node<Integer, Integer> linkedList = getOneWayLinkedListTail();//获得初始化链表---尾插法 
        int size = getOneWayLinkedListSize(linkedList); 
        System.out.println("oneWayLinkedList's size:" + size);//链表长度 
        forLinkedList(linkedList);//打印 
        insertInLinkedList(5, 10, 10, linkedList);//在下标为5的节点之后插入 
        forLinkedList(linkedList);//打印 
        removeInLinkedList(5, linkedList);//在下标为5的节点之后删除 
        forLinkedList(linkedList);//打印 
    } 
 
 
} 

看看循环链表的debug图


再看下我的这几个文件是怎么存放的。



上面的关于循环链表的方法写的有点粗糙,没写完整。先凑合一下吧。



发布评论
IT序号网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

artifact什么意思--刚刚搞web开发的同学可能要问个为什么知识解答
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。