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

前面我们简单的对队列和栈有了个了解,今天我们还要将一种数据结构,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的原理,本文不做研究

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180126G0442U00?refer=cp_1026

相关快讯

扫码关注云+社区