Java实现链表（个人理解链表的小例子）

数组：数组的存储空间是连续的，需要事先申请空间确定大小，通过下标查找数据，所以查找速度快，但是增加和删除速度慢
链表：离散存储，不需要事先确定大小，通过头指针加遍历查找数据，查找数据慢，但是增加和删除速度快

[示例]

在教室里看一下存储空间，同学代表数据

【数组】

int []座位=新的int [5]意味着我从教室（内存空间）申请了第一排座位（数组），座位的标记顺序为1、2、3 ...实现链表，座位[1]意味着坐在第一位置的学生（数据）只能坐在第一行.

查找

无需查找数据. 座位已编号实现链表，老师可以根据座位号（下标）快速要求前几个学生回答问题

这有点麻烦. 第二位同学并不认真. 老师叫他出去. 这时，座位数应减少一. 然后，第三位同学应向左移动一个空格（int [1] = int [2]），依次向左移动一个空格，最后将int [4]腾出，因此最后一个座位应返回到教室（返回到内存），所以这比较麻烦（ps: 我遵循c语言在这里认为，只学习过Java的学生可能很难接受）需要移动座位，这很麻烦

【链接列表】

查找数据（每个学生只知道下一个进来的学生）

删除数据

这种数据结构太形而上. 我学习了很长时间的C语言版本，但我听不懂. 突然有一天，我的大脑开始学习. 估计是菩萨的祝福

现在使用Java代码实现

public class SingleLinkedList<T>{
    //记录链表长度
    private int size;
    //头节点，不存数据，方便实现增删代码的
    private Node head;
    /**
     * 成员内部类，节点类，相当于例子中的同学和座位号的集合题
     * 我觉得这个类不应该暴露给外部
     */
    private class Node{
        private Node next;
        private T t;
        Node(Node next,T t){
            this.next = next;
            this.t = t;
        }
        Node(T t){
            this(null,t);
        }
        Node(){
            Node next = null;
            t = null;
        }
    }
    //链表构造方法
    public SingleLinkedList(){
        //初始化头节点，不存数据，方便实现增删代码的
        this.head = new Node();
        this.size = 0;
    }
    
    /**
     * 此处省略了方法，单独拿出来给大家讲解
     * .........
     */
}

//获取长度
public int getSize(){
    return size;
}

 //添加节点
 public void add(T t){
     Node newNode = new Node(t);
     Node temp = this.head;
     while(temp.next != null){
         temp = temp.next;
     }
     temp.next = newNode;
     size++;
 }

//插入节点，先判断节点是否合法
public void insert(T t,int index){
    if(index <= 0 || index > this.size){
        throw new RuntimeException("index参数不合法");
    }
    Node newNode = new Node(t);
    Node temp = this.head;
    //要明白到底循环几次
    for (int i = 1; i < index; i++) {
        temp = temp.next;
    }
    //注意顺序
    newNode.next = temp.next;
    temp.next = newNode;
    size++;
}

//取节点数据
public T getValue(int index){
    if(index <= 0 || index > this.size){
        throw new RuntimeException("index参数不合法");
    }
    Node temp = this.head;
    //要明白到底循环几次
    for (int i = 0; i < index; i++) {
        temp = temp.next;
    }
    return temp.t;
}

//删除节点
public void delete(int index){
    if(index <= 0 || index > this.size){
        throw new RuntimeException("index参数不合法");
    }
    Node temp = this.head;
    //要明白到底循环几次
    for (int i = 1; i < index; i++) {
        temp = temp.next;
    }
    temp.next = temp.next.next;
    //java垃圾回收机制gc自动回收内存
    size--;
}

//遍历
public void showData(){
    Node temp = this.head;
    //要明白到底循环几次
    for (int i = 0; i < this.size; i++) {
        temp = temp.next;
        System.out.print("["+temp.t+"]-->");
    }
}

【摘要】

个人密码级别有限，仅供参考

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-200555-1.html