算法入门之基本数据结构:链表

前面我们简单的对队列和栈有了个了解，今天我们还要将一种数据结构，Java中很多集合类都是由这几种数据结构演变而来的，除了队列和栈还有我们今天要说的链表，链表其实还是蛮复杂的，在C中有个指针用来实现，很多人说java不存在指针概念，是不是就不能实现链表呢，答案是否，java虽然没有指针但是有对象的引用，我们先看看java中怎么实现链表,然后再来具体分析链表到底是一种怎样的数据结构

代码模拟链表:

public class MyLinkList {
    // 使用数组模拟单向链表
    public static void main(String[] args) {
        //1.通过排序算法已经排好序的一组数
        int[] waitNumbers = {3,6,8,13,15,35};
        int t = waitNumbers.length;
        //2.定义一个数组存放数据
        int[] data = new int[10];
        //3.数据先放入第一个数组
        for (int i = 0; i < waitNumbers.length ; i++) {
            data[i] = waitNumbers[i];
        }
        //4.定义一个数组存下个节点的位置
        int[] nextNode = new int[10];
        //5.初始化已知数组下个节点位置
        for (int i = 0; i < t ; i++) {
            if(i == t-1){
                //说明到了数组最后一位,下个节点不存在
                nextNode[i] = 0;
            }else{
                nextNode[i] = i+1;
            }
        }
        System.out.println(JSON.toJSONString(data));
        System.out.println(JSON.toJSONString(nextNode));
        // 向data中插入一个数字n(10)
        //6.首先要找到插入的数字的位置
        int n = 10;
        for (int i = 0; i < data.length; i++) {
            if(data[i] > n){
                //说明找到了,n应该插在第i-1位上
                data[t] = n;
                nextNode[t] = i;
                t += 1;
                break;
            }else{
                // 数组中的值都比n小,
                data[t] = n;
                nextNode[t-1] = t;
                nextNode[t] = 0;
            }
        }
        System.out.println(JSON.toJSONString(data));
        System.out.println(JSON.toJSONString(nextNode));
    }
}
结果:
存值数组:[3,6,8,13,15,35,0,0,0,0] 
存下个节点位置数组:[1,2,3,4,5,0,0,0,0,0]
插入一个节点10后
存值数组:[3,6,8,13,15,35,10,0,0,0]
存下个节点位置数组:[1,2,3,4,5,6,3,0,0,0]

分析

    Java中经典的链表代表是LinkedList我们今天没有去讲LinkedList如何实现，也没有去讲如何使用他的API，而是自己通过数组实现了一个简单的链表，旨在更方便去理解这种数据结构，通过上述代码我们不难发现链表的一些基本特性：

• 两大基本组成元素：数据块；指向下个节点的存储空间

• 数据为非线性结构

• 基本操作：插入元素；删除元素（删除元素的时候就得实现该元素前一个节点和后一个节点的连接）

链表结构分析如下图

本文只分析链表结构，关于Java中链表的实现有很多以后我们会再具体分析，有兴趣的可以先去了解了解LinkedList的原理，本文不做研究