JAVA，数据结构，链表

JAVA，数据结构，链表 链表

在链表中，每一个元素都可以称之为一个结点。
1.插入：
2.删除：
设计一个类或一个对象表示一个结点

类名Node:T为泛型，可以存储任意类型的数据构造方法Node（T t, Node next）:创建对象成员变量T item :存储数据< br > （item为真正的数据，存的是多少就是多少）成员变量Node next:指向下一个节点，如果当前结点指向的是11，node next 指向的就是12 结点类实现

public class Node{
//存储元素
public T item;
//指向下一个结点
public Node next;
public Node(T item ,Node next){
this.item=item;
this.next=next;
}
}

根据结点构造链表

生成链表：

public static void main(){
//构建结点:创建Node对象，每一个node对象就是一个结点
Node first =new Node(11,null);
Node second=new  Node(13,null);
Node  third =new Node(12,null);
Node fourth =new Node(8,null);
Node fifth =new Node(9,null);
//生成链表
first.next=second;
second.next=third;
third.next=fourth;
fourth.next=fifth;
}

单向链表：结点与结点之间的指向方向只有一个（从左往右或者从右往左）

1.头结点：头结点不存储数据，用他的指针域指向真正存储第一个数据的结点
作用：找到当前链表

单向链表API设计 类名linkList构造方法linkList（）：创建linkList对象成员方法1.public void clear ：空置线性表
2.public boolean isEmpty():判断线性表是否为空，是则返回true，否则返回false
3.public int length():获取元素的个数
4.public Tget(int ):读取并返回线性表中元素的个数
5.public void insert(T t) :往线性表中添加一个元素
6.pubulic void insert (int i, T t) :在索引为i处添加一个T的数据
7.public T remove(int i):删除并返回线性表中第i个元素。
8.public int indexOf(T t):返回线性表中首次出现的指定元素的位序号，若不存在，则返回-1成员内部类prvate class Node:结点类成员变量1.private Node head：记录首结点
2.private int N:记录链表的长度 单向链表的代码实现：详细的解释已经写在代码中了。

public class linkList { //记录头结点
    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() {   //清空链表
        head.next = null;
        this.N = 0;//头结点断开下一个结点，则链表清空
    }
    public int length() {//获取链表的长度
        return -1;
    }
    public boolean isEmpty() {  //判断链表是否为空
        return false;
    }
    public T get(int i) {  //获取指定位置i处的元素
        //通过循环，从头结点开始往后找，依次找i次，就可以找到对应的元素
        Node n = head.next;//需要一个node记录第一个结点，head.next
        for (int index = 0; index < i; index++) {
            n = n.next;//不断地把n向后变化，直到变化的第i个位置处
            //当i循环走完以后，n就是代表i个位置处的结点
        }
        return n.item;
    }
    public void insert(T t) {//向链表中添加元素t
        
        Node n = head;
        while (n.next != null) {
            n = n.next;//如果n.next,为null，证明已经到达最后一个位置
        }
        //创建新的结点，保存元素t
        Node newNode =new Node(t,null);
        n.next=newNode;
        //元素个数+1
        N++;
    }
    //指定在i位置处添加元素
       public void insert ( int i, T t){
            //找到i位置亲的结点，然后创建一个新的结点，让前一个结点指向新的结点，再让新结点指向后面的结点
           //找到i位置处的前一个结点，要有一个东西记录结点。
           Node pre=head;
           for(int index=0;index<=i-1;i++){
               pre=pre.next;
           }
           //找到i位置的结点:上一步动作中已经找到了前一个的结点， 只需要在pre.next就可以找到下一个结点
           // (创建一个curr结点，保存pre.next),
           Node curr=pre.next;
           //创建新的结点:并且新的结点需要指向原来i位置的结点
           Node newNode=new Node(t,curr);
           //原来i位置的前一个结点指向新的结点即可
           pre.next=newNode;
           //元素个数+1
           N++;
        }
        public T remove ( int i){
        //找到i位置的前一个结点，找到位置的结点，找到i位置的下一个结点，全部有了以后，需要前一个位置的结点直接指向下一个位置的结点
            // 前一个结点指向下一个位置的结点
            Node pre=head;
            for(int index=0;index<=i-1;i++){
                pre=pre.next;
            }
            //要找到i位置的前一个结点
            Node curr=pre.next;
            //找到下一个结点
            Node nextNode= curr.next;
            //前一个结点指向下一个结点
            pre.next=nextNode;
            //元素个数-1
            N--;
            return curr.item;
        }
        public int  indexOf(T t){
        //查找出元素t在链表中第一次出现的位置：遍历链表，找到每一个item，判断是否和t一样，如果一样返回下标i就可以了
            //遍历链表，从头节点开始，依次找到每一个结点，去除item，如果相同，就找到了
            Node n=head;
            for(int i=0;n.next!=null;i++){
                n=n.next;
                if(n.item.equals(t)){
                    return i;
                }
            }
        return -1;//如果链表返回-1，则代表，当前链表中并不存在此元素
        }
    }

一天一百行，手感就有了，加油加油！！！