这个链表，以前上学的时候，学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图
再看下我的这几个文件是怎么存放的。
上面的关于循环链表的方法写的有点粗糙，没写完整。先凑合一下吧。
