* 一、什么是双链表
* 每个结点除了保存对下一个结点的引用,同时还保存着对前一个结点的引用
* 二、从头部进行插入
* 要对链表进行判断,如果为空则设置尾结点为新添加的结点,如果不为空,还需要设置设置头结点的前一个结点为新添加的结点
* 三、从尾部进行插入
* 如果链表为空,则直接设置头结点为新添加的结点,否则设置尾结点的后一个结点为新添加结点,同时设置新添加的结点的前一个结点的尾结点
* 四、从头部进行删除
* 判断头部结点是否有下一个结点,如果没有则设置结点为null,否则设置头结点的下一个结点的previous为null
* 五、从尾部进行删除
* 如果头结点后没有其他结点,则设置尾结点为null,否则设置尾结点前一个结点的next为ull,设置尾结点为其前一个结点
* 六、删除方法
* 不需要再使用一个临时的指针域
package com.algorithm; /** * 链表的链结点,相当于车厢 * @author lenovo * */ public class DoubleNode { /** * 数据域 */ public long data; //结点域(指针域),相当于火车与火车的链接 public DoubleNode next; /** * 前一个结点 */ public DoubleNode previous; public DoubleNode(long value){ this.data =value; } /** * 显示方法 */ public void display(){ System.out.print(data+" "); } }
package com.algorithm; /** * 双向链表, * 一、什么是双链表 * 每个结点除了保存对下一个结点的引用,同时还保存着对前一个结点的引用 * 二、从头部进行插入 * 要对链表进行判断,如果为空则设置尾结点为新添加的结点,如果不为空,还需要设置设置头结点的前一个结点为新添加的结点 * 三、从尾部进行插入 * 如果链表为空,则直接设置头结点为新添加的结点,否则设置尾结点的后一个结点为新添加结点,同时设置新添加的结点的前一个结点的尾结点 * 四、从头部进行删除 * 判断头部结点是否有下一个结点,如果没有则设置结点为null,否则设置头结点的下一个结点的previous为null * 五、从尾部进行删除 * 如果头结点后没有其他结点,则设置尾结点为null,否则设置尾结点前一个结点的next为ull,设置尾结点为其前一个结点 * 六、删除方法 * 不需要再使用一个临时的指针域 * @author lenovo */ public class DoubleLinkList { /** * 头结点,相当于火车头 */ private DoubleNode first; /** * 尾结点 */ private DoubleNode last; public DoubleLinkList(){ first =null; last=null; } /** * 插入一个结点,在头结点插入 */ public void insertFirst(long value){ DoubleNode node = new DoubleNode(value); //要对链表进行判断,如果为空则设置尾结点为新添加的结点,如果不为空,还需要设置设置头结点的前一个结点为新添加的结点 if(isEmpty()){ last=node; }else{ first.previous=node; } node.next = first; first =node; } /** * 插入一个结点,在尾结点插入 */ public void insertLast(long value){ DoubleNode node = new DoubleNode(value); //如果链表为空,则直接设置头结点为新添加的结点,否则设置尾结点的后一个结点为新添加结点,同时设置新添加的结点的前一个结点的尾结点 if(isEmpty()){ first=node; }else{ last.next = node; node.previous=last; } last =node; } /** * 删除一个结点,在头结点删除 */ public DoubleNode deleteFirst(){ DoubleNode node = first; //判断头部结点是否有下一个结点,如果没有则设置结点为null,否则设置头结点的下一个结点的previous为null if(first.next==null){ last=null; }else{ first.next.previous=null; } first=node.next; return node; } /** * 删除一个结点,在尾结点删除 */ public DoubleNode deleteLast(){ DoubleNode node = last; //如果头结点后没有其他结点,则设置头结点为null,否则设置尾结点前一个结点的next为ull,设置尾结点为其前一个结点 if(first.next==null){ first=null; }else{ last.previous.next=null; last=last.previous; } return last; } /** * 显示方法 */ public void display(){ DoubleNode current = first; while(current!=null){ current.display(); current = current.next; } System.out.println(); } /** * 查找方法 * @param value * @return */ public DoubleNode find(long value){ DoubleNode current = first; while(current.data!=value){ if(current.next==null){ return null; } current = current.next; } return current; } /** * 删除方法,根据数据域删除 * @param value * @return */ public DoubleNode delete(long value){ //不需要再使用一个临时的指针域 DoubleNode current = first; while(current.data!=value){ if(current.next==null){ return null; } current = current.next; } if(current == first) { first = first.next; } else { current.previous.next = current.next; } return current; } /** * 判断是否为空 * @return */ public boolean isEmpty(){ return first==null; } public static void main(String[] args) { DoubleLinkList linkList = new DoubleLinkList(); linkList.insertLast(45); linkList.insertLast(56); linkList.insertLast(90); linkList.display(); //linkList.deleteLast(); linkList.display(); while (!linkList.isEmpty()) { linkList.deleteLast(); linkList.display(); } } }
相关推荐
JAVA实现链表_双向链表
NULL 博文链接:https://zhanhao.iteye.com/blog/1137409
双端链表和双向链表Java代码
用Java定义一个双向链表,实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。
通过java实现的双向链表,及反转功能,可能对面试有用哦
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
操作包括: 1. 在头部添加结点 2. 在尾部添加结点 3. 遍历 4. 逆置 5. 删除
用java实现双向链表的完整操作,主要用到内部类实现。
自定义的双向链表 博文链接:https://hiliangliang1130-126-com.iteye.com/blog/1144023
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字...为了尽可能少的消耗复制时占用的空间,桶的数据结构选择链表,为了构造队列,选择使用双向列表。
相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的...
Java 有序 非循环 双向 链表 算法 实例
主要介绍了Java实现双向链表(两个版本)的相关资料,需要的朋友可以参考下
二叉树转换为双向链表 通过随机创建二叉排序树测试二叉树转换为双向链表是否正确 http://blog.csdn.net/ssuchange/article/details/17383625
2022年Java语言中链表和双向链表Java教程.docx
在双向链表上实现快速排序的递归算法 输入的形式:元素个数、元素都为整型。 输入值范围:元素个数为非负正整数,需要排序的元素都为整型。 输出的形式:排序前的元素序列和排序后的元素序列。 程序的功能:对用户...
已知N个人(以编号1,2,3...n分别表示)围成一个圈。 从编号为K的人开始报数,数到M的那个人出列,他的下一个人又从1开始报数,依照此规律重复下去,直到圆圈中的人全部出列。 问题:请打印出这N个的...双向链表实现的
Java算法实例-双向链表操作,封装性高,考试、学习都可使用
数据结构之双向链表的Java实现.doc
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...