数据结构之双向链表
例如:现有双向链表TwoWayLinked中存储着1,2,3,4四个元素,那么集合对象中会有4个节点A、B、C、D,由上述结构可以知道,节点A中存储着元素1和节点B;节点B中存储着元素2和节点A和节点C,节点C中存储着元素3和节点B和节点D,节点D中存储着元素4和节点C。如果现在要在元素2和3中间插入一个元素5;
过程如下:
1、创建节点E,E中存储元素5
2、将E中的上一个节点赋值为节点B
3、将B中的下一个节点修改为节点E
4、将E中的下一个节点赋值为节点C
5、将C中的上一个节点修改为节点E
从上述过程看,插入时没有节点位置移动的操作,所以效率比较高;删除的过程和插入过程相反
实例代码:
/**
* TwoWayLinked类
* 演示双向链表这一数据结构的实现
* @author 学霸联盟 - 赵灿
*/
public class TwoWayLinked {
// 用于存储链表的第一个节点
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.pre = node;
first.next = node;
}
//判断最后一个节点是否为null
if(last == null){
/*
* 如果最后一个节点也为null时
* last和first存储的是同一个Node对象的地址
*/
last = node;
}else{
//如果最后一个节点不为null
//新创建的节点前一个节点应该是上一次的最后一个节点
node.pre = last;
//新创建的节点下一个节点存储自身
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 pre;
// 自身类型的变量,用于存储后一个节点
Node next;
// Object类型的变量,用于存储元素
Object element;
}
}
/**
* TwoWayLinkedTest类
* 用于测试双向链表
* @author 学霸联盟 - 赵灿
*/
public class TwoWayLinkedTest {
public static void main(String[] args) {
//创建双线链表的对象
TwoWayLinked twl = new TwoWayLinked();
//向链表中添加值
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已经为我们提供了一系列相应的类来实现基本的数据结构
完整双向链表的实现代码,包括了线性表的基本操作:插入、删除、访问和查找
数据结构双向链表代码,代码结构清晰,很容易读懂,适合初学者学习,100%原装代码。
从初学者的角度深入的分析了内核数据结构的双向循环链表 list_head结构如何构建链表 分析了list_entry LIST_HEAD list_for_each 并最后给出了一个例子以便学习
JAVA实现链表_双向链表
数据结构之双向链表的Java实现.doc
数据结构 双向链表存储 附带基础处理函数 附带测试函数
这是个java编的双向链表的演示,数据结构是编程中很重要,但很难懂的一部分
用Java定义一个双向链表,实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。
数据结构Java双向链表PPT学习教案.pptx
数据结构:双向链表源码,为了让读者有更好的体验,把源码上传上去,有任何问题,或者有任何bug可以直接私信我,我会及时回复,并且解决对应问题
继数据结构源代码之单链表后,双线性链表的C代码实现
这是一个双向链表的实现,集成了删除、添加以及迭代功能
java 数据结构 链表 自己写的 java 数据结构 链表 自己写的 java 数据结构 链表 自己写的
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
数据结构 双向链表的实现
Java算法实例-双向链表操作,封装性高,考试、学习都可使用
Java 有序 非循环 双向 链表 算法 实例
数据结构中的双向链表的代码实现,对初学者有帮助