用Java实现一个简单的单向链表，维护了 head 和 tail。

---

1、Java代码实现

package com.wangjia.datastruc;

/**
 * 单向链表
 * 基础功能: 增 删 取,
 * 说明: 更新维护tail(代价),更快速支持某些操作e.g. addLast(好处).
 *
 * @author : wangjia
 * @time : 2014-08-17 01:55
 */
public class OneWayLinkedList<T> {
    private Node<T> head;

    private Node<T> tail;

    private int len;

    public void add(T t) {
        addToLast(t);
    }

    public void addToFirst(T t) {
        Node<T> newNode = new Node<>(t);
        newNode.next = head;
        head = newNode;
        len++;
    }

    public void addToLast(T t) {
        Node<T> newNode = new Node<>(t);
        if (head == null) {
            tail = head = newNode;
            len++;
            return;
        }
        // 链接到尾部
        tail.next = newNode;
        //维护  tail 和 len
        tail = newNode;
        len++;
    }

    public void add(T t, int index) {
        //长度为3,最多加到 index 4,最多比 len 多1
        checkIndex(index - 1);
        Node<T> newNode = new Node<>(t);
        if (index == 1) {
            addToFirst(t);
            return;
        }
        Node<T> p = this.head;
        //移动次数: index 2 = 0次, index 3 = 1次
        for (int i = 1; i <= index - 2; i++) {
            p = p.next;
        }
        newNode.next = p.next;
        p.next = newNode;
        len++;
    }

    public void rm(int index) {
        checkIndex(index);
        if (index == 1) {
            head = head.next;
            return;
        }
        Node<T> p = this.head;
        //e.g. rm 2 -> 0 次, rm 3 -> 1次
        for (int i = 1; i <= index - 2; i++) {
            p = p.next;
        }
        //
        //如果移除的是 tail ,tail需要新赋值
        if (p.next.next == null) {
            tail = p.next;
        }
        p.next = p.next.next;
        len--;
    }

    public void rmLast() {
        //如果长度为 0 或 1
        if (len == 0 || len == 1) {
            head.value = null;
            head.next = null;
            tail = head;
            len = 0;
            return;
        }
        Node<T> p = head;
        for (int i = 1; i <= len; i++) {
            if (p.next.next == null) {
                p.next = null;
                tail = p;
            }
        }
    }

    public T getFirstAndRm() {
        if (len == 0) {
            return null;
        }
        Node<T> p = this.head;
        head = p.next;
        T val = p.value;
        p = null;
        return val;
    }

    /**
     * 假设链表第一个序号为 1
     */
    public T get(int index) {
        Node<T> p = head;
        checkIndex(index);
        if (index == len) {
            return tail.value;
        }
        //e.g. index 1 -> 0 次移动, index 2 -> 1次移动
        for (int i = 1; i <= index - 1; i++) {
            //右移一次
            p = p.next;
        }
        return p.value;
    }

    public T getFirst() {
        if (head != null) {
            return head.value;
        }
        return null;
    }

    public T getLast() {
        if (head != null) {
            return head.value;
        }
        return null;
    }

    /**
     * @return len
     */
    public int len() {
        return len;
    }

    @Override
    public String toString() {
        if (head == null) {
            return "len:0";
        }
        StringBuilder s = new StringBuilder("len:");
        s.append(len).append("values:[ ");
        Node<T> p = this.head;
        for (int i = 1; i <= len; i++) {
            s.append(p.value).append(",");
            p = p.next;
        }
        s.append("]");
        return s.toString();
    }

    private static class Node<T> {
        Node<T> next;
        T value;

        public Node() {
        }

        public Node(Node<T> next, T value) {
            this.next = next;
            this.value = value;
        }

        public Node(T value) {
            this(null, value);
        }
    }

    private void checkIndex(int index) {
        if (index > len) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + len;
    }
}

2、简单测试


package com.wangjia.datastruc.test;

import com.wangjia.datastruc.OneWayLinkedList;
import org.junit.Assert;
import org.junit.Test;

public class OneWayLinkLinkTest {
    /**
     * 单链表测试
     */
    @Test
    public void testMyLinkList() {
        OneWayLinkedList<String> list = new OneWayLinkedList<>();
        Assert.assertEquals("len ", list.len(), 0);

        list.add("1");
        list.add("2");
        list.add("3");// 1 2 3
        Assert.assertEquals("len", list.len(), 3);
        Assert.assertEquals("value check 1", list.get(1), "1");
        Assert.assertEquals("value check 2", list.get(2), "2");
        Assert.assertEquals("value check 3", list.get(3), "3");

        list.add("5", 2); // 1 5 2 3
        Assert.assertEquals("value check add index ", list.get(1), "1");
        Assert.assertEquals("value check add index ", list.get(2), "5");
        Assert.assertEquals("value check add index ", list.get(3), "2");

        list.add("6", 1); // 6 1 5 2 3
        Assert.assertEquals("value check add index", list.get(1), "6");
        Assert.assertEquals("value check add index", list.get(2), "1");

        list.rm(1);  // 1 5 2 3
        Assert.assertEquals("after rm", list.get(1), "1");
        list.rm(3); // 1 5 3
        Assert.assertEquals("after rm", list.get(3), "3");
    }
}