概念：

链表结构，是基于指针实现的，由一个个节点组成，每个节点包含数据域和指针域，节点通过指针域进行关联。

链表既可以是连续的，也可以是不连续的，总之都是线性表结构。

链表类型可以分这几类：

• 单链表
• 循环链表
• 双向链表
• 双向循环链表

我打算从最简单的单链表开始学习。

单链表

链表的每个节点中只包含一个指针域，叫做单链表

单链表中的节点结构

• 数据域
• 指针域

如图：

用代码表示：

//链表中的节点

public class P<T> {
    //数据
    T data;
    //指针
    P<T> next;

    public P(T data,P<T> next ){
        this.data = data;
       this.next = next;
    }

}

单链表，就是通过指针域持有下个节点的引用来进行关联，比如P0.next–>P1 用代码来表示就是，new P0().next=new P1();

一直这样关联下去P1.next–>P2，P2.next–>P3

代码实现：

首先是节点

public class P<T> {
    //数据
    T data;
    //指针
    P<T> next;

    public P(T data,P<T> next ){
        this.data = data;
       this.next = next;
    }

}

接着是链表的实现

public class LinkedP<T> {
    //节点数量
    private int mSize;
    //头节点
    private P<T> mFirst;
    //最后的节点
    private P<T> mLast;
    //链表被操作的次数
    private int mModCount;
    /**
     * 添加数据--默认添加到最后面
     * @param data
     */
    public void add(T data){
        P<T> l=mLast;
        P<T> newP=new P<>(data,null);
        mLast=newP;
        if(l==null){
            mFirst=newP;
        }else{
            l.next=newP;
        }
        mSize++;
        mModCount++;
    }

    public void add(T data,int index){
        checkPositionIndex(index);
        if(index==mSize){
            add(data);
        }else{
            linkBefore(data,index);
        }
    }

    //再之前插入
    private void linkBefore(T data, int index) {
        P<T>[] nodes = getNodes(index);
        //index当前的节点
        P<T> x=nodes[0];
        //上一个
        P<T> pre=nodes[1];
        //要插入的节点
        P<T> newP=new P<>(data,x);
        pre.next=newP;
        mSize++;
        mModCount++;
    }

    //获取当前节点和当前节点的前节点
    private P<T>[] getNodes(int index){
        P<T>[] ps= new P[2];
        P<T> node = mFirst;
        P<T> pre=null;
        int i=0;
        while (i<index){
            if(i==index-1){
                pre=node;
            }
            node=node.next;
            i++;
        }
        ps[0]=node;
        ps[1]=pre;
        return ps;
    }

    //移除操作
    public void remove(int index){
        checkPositionIndex(index);
        P<T>[] nodes = getNodes(index);
        //当前要删除的节点
        P<T> x = nodes[0];
        //前一个节点
        P<T> pre = nodes[1];
        pre.next=x.next;
        x=null;
        mSize--;
        mModCount++;
    }

    //获取数据
    public T get(int index){
        checkPositionIndex(index);
        P<T>[] nodes = getNodes(index);
        P<T> node = nodes[0];
        return node.data;
    }

    //设置数据
    public void set(T data,int index){
        checkPositionIndex(index);
        P<T>[] nodes = getNodes(index);
        P<T> node = nodes[0];
        node.data=data;
    }

    //获取链表的size
    public int getSize(){

        return mSize;
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+mSize);
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= mSize;
    }
    /**
     * 打印整个链表
     */
    public void printAll() {
        if (mSize != 0) {
            for (P<T> p = mFirst; p != null; p=p.next ) {
                System.out.print(p.data.toString() + " ");
            }
        }

    }
}

代码测试：

public class Test {

    public static void main(String[] args) throws Exception {
        LinkedP<Integer> linkedP=new LinkedP<>();
        for (int i = 0; i < 10; i++) {
            linkedP.add(i);
        }
        //
        System.out.print("\n======== 默认打印 ======\n");
        linkedP.printAll();
        System.out.print("\n======== 设置数据99 ======\n");
        linkedP.set(99,3);
        linkedP.printAll();
        System.out.print("\n======== 再某个位置添加数据 ======\n");

        linkedP.add(-10,6);
        linkedP.printAll();
        System.out.print("\n======== 删除最后一个数据 ======\n");
        linkedP.remove(linkedP.getSize()-1);
        linkedP.printAll();
        }
    }

结果：