数据在计算机内有两种存储结构,一种是顺序结构,另一种是树形(索引)结构。在顺序结构里面一般分为数组和链表两种结构。数组是一种物理地址上连续,即在内存中为连续的一个块。而链表是一种逻辑上的连续,数组可以通过下标来查找到数组中的一个值。而链表是通过一个根节点开始遍历来查找值。
数组与链表各有优缺点。数组方便查找。链表方便插入与删除等修改操作。
数组的结构大家应该都有所了解。这里讲一讲链表的数据结构,它是一种链式的,形象的说就是一环紧扣一环的形状。有一种顺藤摸瓜的意思,每一个链表中的节点都连着它的上一节点与下一节点,要想找到一个目标节点就要知道它的上一个节点是谁。那么所有节点的根源就是那个根节点。每个节点都有一个数据域与child域(标准化的说法),数据域就是此节点内保存的data,而child域里面存的就是它的下一个节点,它指向了它下一个是谁。
所以我们如果要进行增删改查的操作就很方便了,如果要删除某个节点,只需将此节点的child域指向null,并且将此节点的上一个节点指向本来此节点的下一个节点。这样它就退出了这个链表。插入操作也是同样的原理。只需修改child域,当然,如果要更加方便的话我们可以在节点中再增加一个parent域,这样就是双向链表了。不仅可以正着遍历,也可以倒着遍历。
下面给出链表的源代码:
首先定义节点及其成员变量
package LinkListTest;
/**
* 链表节点
*
* @author bug
*
*/
public class linkNode {
// 节点内的数据对象
private Object obj;
//对下一个节点的引用
private linkNode next;
/**
* 带节点数据的构造方法
* @param obj
*/
public linkNode(Object obj){
this.obj=obj;
}
public linkNode(){
}
/**
* 返回节点内数据
* @return
*/
public Object getObj(){
return obj;
}
/**
* 设置节点数据
* @param obj
*/
public void setObj(Object obj){
this.obj=obj;
}
/**
* 设置当前结点的下一个节点
* @param next
*/
public void setNext(linkNode next){
this.next=next;
}
/**
* 得到下一节点
* @return
*/
public linkNode getNext(){
return next;
}
}
然后进行链表的创建并运行:
package LinkListTest;
/**
* 链表
*
* @author bug
*
*/
public class linkList {
public static int count = 0;
public static linkNode root = null;
public static linkNode tail = null;
public static void main(String[] args) {
linkList list = new linkList();
for (int i = 1; i < 4; i++) {
list.addNode(i);
}
//打印链表
list.printList(root);
//得到第2个元素
linkNode n = list.getNode(2);
System.out.println("得到的元素是"+n.getObj());
//在2号位插入元素
list.insertNode(1, "插入元素i");
//打印链表
list.printList(root);
}
/**
* 创建链表
*
* @return
*/
public void addNode(Object data) {
//实例化一个节点
linkNode node = new linkNode(data);
//如果插入节点时链表为空。姐将插入的节点设为根节点,尾节点的指针下一个节点设置为空
if (root == null) {
root = node;
tail = root;
tail.setNext(null);
}
//否则将新节点插入链表尾,更新尾节点
else {
tail.setNext(node);
tail = node;
tail.setNext(null);
}
count++;
}
public void insertNode(int index, Object data) {
//如果待插入下标非法,退出
if (this.size() < index || index < 0) {
System.out.println("下标值非法");
return;
}
//正确下标时,实例化一个待插入节点,实例化一个遍历链表的节点
linkNode newNode = new linkNode(data);
linkNode pNode = new linkNode();
//将遍历节点初始化为根节点
pNode = root;
//当不是把插入节点作为根节点时,就是不在第一个位置插入元素时
if(this.getNode(index)!=root){
//循环pNode为下标index的上一个节点
while(pNode.getNext()!=this.getNode(index)){
pNode=pNode.getNext();
}
//将新节点插到pNode后面
newNode.setNext(pNode.getNext());
pNode.setNext(newNode);
}
//当是把插入节点作为根节点时,将新节点插入链表头
else{
newNode.setNext(root);
root=newNode;
}
}
/**
* 得到第index个节点
*
* @param index节点数
* @return返回节点
*/
public linkNode getNode(int index) {
linkNode node = new linkNode();
if (index > this.size()) {
Exception e = new Exception();
System.out.println("下标非法");
}
node = root;
index--;
while (index > 0) {
node = node.getNext();
index--;
}
return node;
}
/**
* 打印链表
*
* @param root
*/
public void printList(linkNode root) {
if (root != null) {
// 得到根节点数据
Object data = root.getObj();
// 输出根节点数据
System.out.println(data);
// 根节点指向下一个节点
linkNode temp = root.getNext();
// 递归
printList(temp);
}
}
public int size() {
return count;
}
}
分享到:
相关推荐
数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表
算法-数据结构之链表合并算法.rar
C通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构...
数据结构 数据结构_使用javascript讲解数据结构之链表
C语言中数据结构之链表归并排序实例代码 问题 设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中...
基础数据结构之链表
线性表的存储结构使用链表。 2、提供操作:自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。 3、接收键盘录入的一系列整数(例10,25,8,33,60)作为节点的元素值,创建链表。输出链表内容。 4、输入...
自己写的 数据结构之链表栈与队列 出来与同路的新手分享
数据结构之链表.ppt该文档详细且完整,值得借鉴下载使用,欢迎下载使用,有问题可以第一时间联系作者~
这是一个链表的代码,它对于初学者来说是一个有很好帮助的东西,完全是自己写的,已经通过编程测试,供大家一起来分享!
1.使用Python语言实现链表数据结构 2.基于类封装思想 3.实现链表增删改查功能 4.有测试数据
数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现
本文实例讲述了JS中的算法与数据结构之链表(Linked-list)。分享给大家供大家参考,具体如下: 链表(Linked-list) 前面我们讨论了如何使用栈、队列进行存数数据,他们其实都是列表的一种,底层存储的数据的数据结构都...
单链表 单循环链表 双链表 双循环链表 内容学习于 https://www.bilibili.com/video/BV1W64y1z7jh?p=19&spm_id_from=pageDriver&vd_source=4d33bf4ac4499f2c0370694554a02fa5
主要是针对c++中的链表模版进行了实现,希望可以帮助需要的人
C++数据结构之链表的创建 前言 1.链表在C/C++里使用非常频繁, 因为它非常使用, 可作为天然的可变数组. push到末尾时对前面的链表项不影响. 反观C数组和std::vector, 一个是静态大小, 一个是增加多了会对之前的元素...
list v2 用Object对象,接口inteface,迭代器Iterator实现linklist,Arraylist