Java如何实现单链表

问题描述

数据结构在计算机科学中是一门综合性的专业基础课，因此对于它的理解是很重要。数据的储存结构分为顺序存储结构和链式存储结构。前一种存储结构则需要在内存中使用一块连续的内存去进行存储，通常借助程序设计语言的数组来描述。后一种存储结构无需保证元素在内存存储位置上的连续性，只需要在逻辑上相邻的元素之间用指针来指定，通常借助程序设计语言的指针类型来描述。

而Java中并没有显示的指针，无法得到每个元素的地址，那如何使用Java实现单链表呢？

解决方案

单链表：为了表示每个数据元素ai (i为下标)于其直接后继数据元素ai+1（i+1为下标）之间的逻辑关系，对数据元素ai来说，除了存储器本身的信息之外，还需要一个指示其直接后继的信息（即直接后继的存储位置）。这两个部分组成数据元素ai的存储映像，称为结点（node），第一部分为数据域，第二部分为指针域。指针域内存储着指针或链对于单链表来说，每个结点只包含一个指针域。

通常会为其链表增加头结点，便于对首元结点的处理和空表、非空表的统一处理。

语言只是一个表达的工具，数据结构真正需要了解的是它的思想，百变不离其中。

Java实现单链表

（1）单链表初始化：编写一个Node类来充当结点的模型。我们知道，其中有两个属性，1数据域，2指针域。

（2）增加结点操作：

1在链表的最后进行插入操作：head为头节点，指向了第一个存储的数据元素结点，应用遍历进行判断是否还有下一个结点，当没有结点时则进行插入操作。

2在指定位置进行插入操作：参数index想要插入的位置，node插入的结点。首先在最初判断插入的位置是否合法，若合法则依次遍历计数到指定位置结束。

结语

由于Java语言中没有指针，因此可以将每个结点包装成类，利用其中一个成员属性将一个一个单独的结点连接起来。对于数据结构，语言的选择不会影响它的表达，真正理解它的意义才更为重要。