数据结构之单向链表
例如:现有双向链表OneWayLinked中存储着1,2,3,4四个元素,那么集合对象中会有4个节点A、B、C、D,由上述结构可以知道,节点A中存储着元素1和节点B;节点B中存储着元素2和节点C,节点C中存储着元素3和节点D,节点D中存储着元素4和null。如果现在要在元素2和3中间插入一个元素5;
过程如下:
1、创建节点E,E中存储元素5
2、将B中的下一个节点修改为节点E
3、将E中的下一个节点赋值为节点C
从上述过程看,插入时没有节点位置移动的操作,所以效率比较高;删除的过程和插入过程相反;和双向链表的区别就是一个节点中不再存储上一个节点
实例代码:
/**
* OneWayLinked类
* 演示双向链表这一数据结构的实现
* @author 学霸联盟 - 赵灿
*/
public class OneWayLinked {
// 用于存储链表的第一个节点
private Node first = null;
// 用于存储链表的最后一个节点
private Node last = null;
// 用于存储集合长度
private int size = 0;
//添加元素的方法
public void add(Object obj){
//创建节点对象
Node node = new Node();
//节点中存储添加的元素
node.element = obj;
//判断第一个节点是否为null
if (first == null) {
//第一个节点为说明是第一次添加元素
first = node;
//将第一个节点的后一个节点都设置成自己
first.next = node;
}
//判断最后一个节点是否为null
if(last == null){
/*
* 如果最后一个节点也为null时
* last和first存储的是同一个Node对象的地址
*/
last = node;
}else{
//如果最后一个节点不为null
//新创建的节点下一个节点存储自身
node.next = node;
//此时last中保存的还是上一次添加元素时的最后一个节点
//所以它的下一个节点应该设置为当前新建的节点
last.next = node;
//然后将last设置为当前新建的节点
last = node;
}
//添加元素,长度加1
size++;
}
/**
* 根据下标获取元素
*/
public Object get(int index) {
//首先判断传入的下标是否超出长度
if (index < size) {
/*
* 声明一个Node类型的变量tagNode,并设置为first
* 表示寻找的时候从第一个节点开始找
*/
Node tagNode = first;
for (int i = 0; i < index; i++) {
//获取下一个节点,等价于i+1
tagNode = tagNode.next;
}
//获取找到的节点中的元素
return tagNode.element;
}
//如果传入的下标大于或等于长度,返回null
return null;
}
/**
* 节点类(私有的成员内部类)
*
* @author 学霸联盟 - 赵灿
*/
private class Node {
// 自身类型的变量,用于存储后一个节点
Node next;
// Object类型的变量,用于存储元素
Object element;
}
}
/**
* OneWayLinkedTest类
* 用于测试双向链表
* @author 学霸联盟 - 赵灿
*/
public class OneWayLinkedTest {
public static void main(String[] args) {
//创建双线链表的对象
OneWayLinked twl = new OneWayLinked();
//向链表中添加值
twl.add(1);
twl.add(2);
twl.add(3);
twl.add(4);
//获取下标为2的值
Object element = twl.get(2);
//输出值
System.out.println(element);
}
}
运行结果:
3
版权声明:本文为博主原创文章,未经博主允许不得转载。
分享到:
相关推荐
Java 数据结构 链表 Java链表 数据结构链表
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现...
java语言模拟单向链表,JAVA数据结构
这是一个单向链表,它具有插入与删除节点的功能。Entry类实现了链表的各节点。
java 数据结构 链表 自己写的 java 数据结构 链表 自己写的 java 数据结构 链表 自己写的
数据结构:单向链表源码,为了让读者有更好的体验,把源码上传上去,有任何问题,或者有任何bug可以直接私信我,我会及时回复,并且解决对应问题
C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
数据结构第一章 第二章的一些小程序,包括单向链表,双向链表,a交b等等
用c语言实现单向链表的数据结构,可以在编译器里直接使用的
数据结构:单向循环链表源码,为了让读者有更好的体验,把源码上传上去,有任何问题,或者有任何bug可以直接私信我,我会及时回复,并且解决对应问题
数据结构实验报告,使用vC++ 6.0工具来进行调试单向链表。
#资源达人分享计划#
数据结构 链表 C语言 单向链表 栈
java 数据结构 遍历链表程序 有研究或探讨的请加群:37424970 或联系本人MSN或邮箱:zhuseahui@yahoo.com.cn
数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表
数据结构-链表 JAVA语言实现,包含单向链表、双向链表、循环链表的遍历、删除和插入 详细介绍:http://blog.csdn.net/z740852294/article/details/77369439
数据结构实验——链表 数据结构实验——链表
04.单向链表以及单向链表的应用.ppt
C#单向链表的实现的源码