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

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

代码模拟链表:

public classMyLinkList{

// 使用数组模拟单向链表

public static voidmain(String[]args) {

//1.通过排序算法已经排好序的一组数

int[] waitNumbers={3,6,8,13,15,35};

intt=waitNumbers.length;

//2.定义一个数组存放数据

int[] data= new int[10];

//3.数据先放入第一个数组

for(inti=;i

data[i]=waitNumbers[i];

}

//4.定义一个数组存下个节点的位置

int[] nextNode= new int[10];

//5.初始化已知数组下个节点位置

for(inti=;i

if(i==t-1){

//说明到了数组最后一位,下个节点不存在

nextNode[i]=;

}else{

nextNode[i]=i+1;

}

}

System.out.println(JSON.toJSONString(data));

System.out.println(JSON.toJSONString(nextNode));

// 向data中插入一个数字n(10)

//6.首先要找到插入的数字的位置

intn=10;

for(inti=;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]=;

}

}

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的原理，本文不做研究