单向链表

链表

什么是链表

链表是一种物理存储单元上非连续性，非顺序的存储结构，其物理结构不能直观的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。

结点API设计：

单向链表API设计

单向链表代码实现

public class LinkList<T> implements Iterable<T>{
    private Node head;      //记录首结点
    private int N;  //记录链表的长度

    private class Node{
        //储存数据
        T item;
        //下一个结点
        Node next;
        public Node(T item,Node next){
            this.item = item;
            this.next = next;
        }
    }

    public LinkList(){
        //初始化头结点
        this.head = new Node(null,null);
        //初始化元素个数
        this.N = 0;
    }

    /**
     * 清空线性表
     */
    public void clear(){
        this.head.next = null;
    }

    /**
     * 判断线性表是否为空
     */
    public boolean ifEmpty(){
        return this.head.next==null;
    }

    /**
     * 获取线性表中元素的个数
     */
    public int length(){
        return N;
    }

    /**
     * 读取并返回线性表中第i个元素
     */
    public T get(int i){
        Node n = head.next;
        for(int index=0;index<i;index++){
            n=n.next;
        }
        return n.item;
    }

    /**
     * 往线性表中添加一个元素
     */
    public void insert(T t){
        Node n=head;
        while(n.next!=null){
            n=n.next;
        }
        Node insertT = new Node(t,null);
        n.next = insertT;
        N++;
    }

    /**
     * 在链表第i个元素前面添加一个元素
     */
    public void insert(int i,T t){
        Node n=head;
        //首先找到第i个位置
        for(int j=0;j<i-1;j++){
            n=n.next;
        }
        //找到i位置的结点
        Node curr = n.next;
        //创建新的结点
        Node insertT = new Node(t,curr);
        n.next = insertT;
        N++;
    }
    /**
     * 删除并返回线性表中第i个元素
     */
    public Node remove(int i){
        Node n=head;
        //首先找到第i个元素的前面一个元素
        for(int j=0;j<i-1;j++){
             n=n.next;
        }
        Node deleteData = n.next;
        //找到即将要删除的元素
        Node nextData = deleteData.next;
        //将i前面的元素的下一个结点改变成删除元素的下一个结点。
        n.next = nextData;
        return deleteData;
    }

    /**
     * 返回顺序表中首次出现的指定数据元素的位序号，若不存在则返回-1
     */
    public int indexOf(T t){
        Node n = head;
        //首先遍历整个顺序表，查看是否有哪个元素是匹配的
        for(int j=0;n.next!=null;j++){
            n=n.next;
            if(n.item.equals(t)){
                return j;
            }
        }
        return -1;
    }
    @Override
    public Iterator<T> iterator() {
        return null;
    }

    public class LIterator implements Iterator{
        private Node n;
        public LIterator(){
            this.n= head;
        }
        public boolean hasNext(){
            return n.next!=null;
        }

        public Object next(){
            n=n.next;
            return n.item;
        }
    }
}