写一个大家都比较熟悉的数据结构:单向链表。
不过先告诉大家一个小秘密,java的API里面已经提供了单向链表的类,大家可以直接拿来用,不过学习数据结构课程的时候想必大家也已经知道,虽然系统会给我们提供一些常用的数据结构,但是自定义的总是能够带来不同的喜感的,而且通过自己的编写也更能够让我们了解其中实现的过程,而且我们还可以写一些比较个性化的方法作为属于自己的数据结构。这里主要是介绍一些常用结构里面都会用到的方法,以及链表具体是如何操作的。
首先,单链表相对于队列的优势在于存储地址不是连续的,这样的意义在于,操作其中的某一个位置的元素时不需要对之前的其他元素都进行内存操作,大大的为我们的计算机减压了。下面直接进入正题:
先要定义一个结点类,如下:
public class Node { Node next;//下一个结点的引用 Object obj;//结点元素 public Node(Object obj){ this.obj=obj; } }
然后就是我们的LinkedList类,先要定义一个空链表:
Node head=null;//创建一个空链表,头结点
Node last=head;//尾结点
打印链表有两种方法,可以采用递归,也可以使用非递归的方法,如下:
/** * 非递归打印元素的方法 */ public void print(Node head){ while(head!=null){ System.out.println(head.obj); head=head.next;//索引向后移位 } } /** * 递归打印链表元素的方法 */ public void printNode(Node head){ if(head!=null){ System.out.println(head.obj); Node node=head.next; printNode(node);//递归调用 } }
非递归方法有一个致命的缺陷,打印的同时改变了头结点的位置,所以我们应该倾向于使用递归方法。
说了这么多,增删查改正式开始:
向链表中添加元素。判断一个链表已经到达末尾的依据是该结点的next引用已经为Null,所以要向末尾添加一个结点,先要把新增结点放在最后,再把末尾结点向后移位,具体操作过程如下图:
代码如下:
/** * 向指定链表添加元素的方法 * @param obj 插入的元素 */ public void add(Object obj){ Node node=new Node(obj);//新建结点 if(head==null){//如果链表为空 head = node; }else{ last.next=node;//先把新增结点放在最后 } last=node;//再把最后一个结点向后移位 }
插入元素。要插入一个新元素首先要创建一个新结点来存放它,而在具体实现的时候最让人头疼的时候无疑是怎样找到指定位置的索引了,这里所说的方法在下面的其他操作基本上都是这样衍生的,先了解一下插入结点的具体实现,根据这个结构的逻辑定义,如果我们要在结点A之后插入一个结点,那么就还需要修改结点A的next引用,实际上就是让A结点的next引用指向新增结点的元素域,然后再让新增结点的next引用指向A原本next结点(B)的元素域,用图来表示更加直观:
代码如下:
/** * 向链表中插入新元素的方法 */ public void insert(int index,Object obj){ Node node=head; int j=0; while(node!=null&&j<index-2){ //查找到第index-1个元素 node=node.next; j++; } Node sert=new Node(obj);//被插入的结点 sert.next=node.next; node.next=sert; }
删除元素。知道了插入元素的具体操作之后,删除元素就显得相对简单了,比如说我们要删除一个结点b,就是要使这个结点失去引用,但是注意不要直接写b=b.next,这样的话b的引用还是存在,而且还会出现另一种错误,大家可以自己试一下,如图所示,正确的删除结点的方法如下:
代码如下:
/** * 删除指定位置的结点 * @param index 索引 */ public void delete(int index){ Node node=head; int j=0; while(node!=null&&j<index-2){ //查找到第i-1个元素 node=node.next; j++; } node.next=node.next.next;//删除第index个元素 }
最后就是修改元素了。相信大家看完之前的两个方法,接下来的这个方法在心中早就已经泛起波澜了吧,那下面就直接贴代码了:
/** * 改变指定位置的元素 * @param index 索引 * @param obj */ public void modify(int index,Object obj){ Node node=head; int j=0; while(node!=null&&j<index-1){ //找到第index个结点 node=node.next; j++; } node.obj=obj; }
当然,除了这些基本操作,我们还可以写获取链表长度的方法,获取指定位置的元素的方法等等,这里就不一一介绍了,主要是让大家熟悉一下这个数据结构。最近一阵学校课程太多,心里有很多想法却一直开不了口啊,慢慢来吧,学习也不是一天两天的事情,这几天都没搞锻炼了,今天在教室考试的时候就有人突然癫痫犯了,做技术的更应该关注自己的身体,加油。。。
相关推荐
简单的单向链表,增删查改练习。简单的二叉树练习,适合初学者,简单易懂,非常实用。VS2015工程,可以直接运行。
此压缩包为1、无头+单向+非循环链表增删查改实现// 动态申请一个结点// 单链表打印// 单链表尾插// 单链表的头插// 单链表的尾删// 单链表头删// 单链表查找// 单链表在pos位置之后插入x// 单链表删除pos位置之后的...
入门第24天写的代码 基于 双向链表和单向链表的 增删查改的 记录航班 添加航班 查找 删除航班啥的小白一个 希望大神不要嘲笑哈哈
在数组上完成数据的增删查改。顺序表一般可以分为静态顺序表和动态顺序表。 2.2 接口实现 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。...
增删查改操作相对顺序表更灵活,但访问元素不如顺序表直接。 顺序表和链表的主要区别在于存储方式和元素访问效率。顺序表适合于随机访问,插入和删除操作在元素数量较大时效率降低;而链表在插入和删除操作上更高效...
在学生管理系统中,它允许我们高效地管理学生数据,方便地进行增删查改操作,同时保持数据的有序性。对于初学者来说,这是一个很好的实践项目,有助于加深对数据结构的理解,并提升编程技能。通过阅读和分析`two_way...
实现功能分权限(教师,学生),教师功能有信息增删查改,读写文件,成绩排序,学生功能有信息查询。数据结构采用单向链表,具体功能与实现思路在文档中,适合c语言新手学习的项目。
- **双向链表**提供前向和后向遍历的能力,方便联系人信息的增删查改,同时需要良好的用户界面和错误处理机制。 7. **一元稀疏多项式计算器**: - **链表**用于存储稀疏多项式,减少存储空间,支持多项式的输入、...
单向链表只包含指向下一个节点的指针,而双向链表则包含指向前一个节点和下一个节点的两个指针,这为数据的增删查改提供了更多可能性。 在这个项目中,"任务书"可能详细阐述了系统应具备的功能,比如添加学生信息、...
5. **集合类**:如`List<T>`、`ArrayList`和`HashSet<T>`等,提供了丰富的数据操作方法,方便程序员进行增删查改操作。 6. **哈希表**:如`Dictionary, TValue>`,基于键值对存储,通过哈希函数快速查找,适合大量...