Java实现单链表

概念介绍

以“结点的序列”表示线性表称作线性链表（又称单链表），是一种链式存取的数据结构。

用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

存储方式

链接方式存储的线性表简称为链表（Linked List）。
链表的具体存储表示为：
① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

结点结构

┌───┬───┐
│data │next │
└───┴───┘
data域–存放结点值的数据域
next域–存放结点的直接后继的地址（位置）的指针域（链域）
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。

Java实现

/**
 *  单链表实现
 * 
 *  @author Java猿人一枚
 */
class SingleLinkedList<E> {
    private Node<E> head;
    private int size;

    public SingleLinkedList() {

    }

    public void print(){
        Node<E> node = this.head.next;
        System.out.print(head.value + "\t");
        while(node != null){
            System.out.print(node.value + "\t");
            node = node.next;
        }
    }

    public void addHead(E e){
        this.addNode(e, 0);
    }

    public void addNode(E e, int position){
        //1.判断position的有效性[0, size]之间
        if(position > size || position < 0){
            System.out.println("请输入正确的position值！");
        }
        Node<E> newNode = new Node<>(e);
        if(position == this.size){
            //2.position==size
            if(this.head == null){
                //head为null表示size=0
                this.head = newNode;
            }else{
                //放最后
                Node<E> temp = this.head;
                while(temp.next != null){
                    temp = temp.next;
                }
                temp.next = newNode;
            }
        }else{
            //3.else，
            if(0 == position){
                //放最前
                Node<E> temp = this.head;
                this.head = newNode;
                newNode.next = temp;
            }else{
                //找到position-1和position位置的节点,将插入节点放到中间位置
                Node<E> pNode = node(position);
                Node<E> preNode = node(position-1);
                preNode.next = newNode;
                newNode.next = pNode;
            }
        }
        size++;
    }

    /**
     * 找到position位置的节点
     *
     * @param position
     * @return
     */
    public Node<E> node(int position){
        Node<E> x = this.head;
        for (int i = 0; i < position; i++){
            x = x.next;
        }
        return x;
    }

    public int size(){
        return this.size;
    }

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public static class Node<E>{
        Node<E> next;
        E value;

        public Node(E value) {
            this.value = value;
        }
    }
}

测试

/**
 * 测试单链表
 */
public static void testSingleLinkedList(){
    SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();
    singleLinkedList.addHead(1);
    singleLinkedList.addHead(2);
    for(int i = 2; i < 5; i++){
        singleLinkedList.addNode(i+1, i);
    }
    singleLinkedList.addHead(10);
    singleLinkedList.addNode(8,3);
    singleLinkedList.addNode(0, 0);
    //预想结果打印：0 10 2 1 8 3 4 5
    singleLinkedList.print();
}