Java链表实现：理解链表的核心操作

前言作为大二数据结构课程的重点内容链表是一种基础且重要的线性数据结构。相比于数组链表在插入、删除操作上更灵活不需要连续的内存空间。本文基于自己手写的链表代码详细解释链表常用方法的实现思路帮助大家理解链表的核心操作逻辑。1.链表的基础结构首先定义链表的节点类Node每个节点包含两部分存储的数据x和指向下一个节点的指针next。publicclassNodeE{Ex;// 节点存储的数据Nodenext;// 指向下一个节点的指针// 带参构造方法初始化节点数据publicNode(Ex){this.xx;}// 无参构造方法publicNode(){}}接着通过test类实现链表的核心操作类中定义了两个关键的静态指针• head头节点指针指向链表的头节点头节点不存储有效数据仅作为链表入口• tail尾节点指针指向链表的最后一个节点方便尾部插入操作。2.链表核心方法详解1. 元素添加方法1尾部添加元素add(Object o)功能在链表的最后一个节点后添加新元素利用tail指针直接定位到尾部无需遍历链表。实现逻辑• 判断尾节点tail是否为空 • 创建新节点并赋值 • 将尾节点的next指向新节点再将tail指针移动到新节点 • 添加成功返回true否则返回false。Overridepublicbooleanadd(Objecto){if(tail!null){NodeObjectnewnodenewNodeObject(o);tail.nextnewnode;tailtail.next;returntrue;}else{returnfalse;}}2指定索引插入元素add(int index, Object o)功能在链表指定索引位置插入元素索引从 0 开始。实现逻辑• 创建新节点并赋值• 遍历链表到目标索引的前一个节点• 将新节点的next指向原索引位置的节点再将前一个节点的next指向新节点。Overridepublicvoidadd(intindex,Objecto){NodeObjectnewnodenewNodeObject(o);Nodecurhead.next;for(inti0;iindex;i){curcur.next;}newnode.nextcur.next;cur.nextnewnode;}3头部添加元素addFirst(Object o)功能在链表头部头节点后插入新元素。实现逻辑• 创建新节点并赋值• 新节点的next指向原链表的第一个有效节点head.next• 头节点的next指向新节点完成头部插入。OverridepublicvoidaddFirst(Objecto){NodeObjectnewnodenewNodeObject(o);newnode.nexthead.next;head.nextnewnode;}4尾部添加元素重载addLast(Object o)功能与add(Object o)功能一致专门用于尾部插入语义更明确。实现逻辑直接通过tail指针在尾部创建新节点更新tail指针。OverridepublicvoidaddLast(Objecto){NodeObjectnewnodenewNodeObject(o);tail.nextnewnode;tailtail.next;}2. 元素删除方法1删除第一个出现的指定元素removefirstappear(Object o)功能遍历链表删除第一个匹配目标值的节点。实现逻辑• 从head开始遍历找到目标元素的前一个节点• 若删除的是尾节点需将尾节点指针tail更新为前一个节点并将前一个节点的next置空• 否则直接将前一个节点的next指向目标节点的下一个节点• 删除成功返回true否则返回false。Overridepublicbooleanremovefirstappear(Objecto){Nodecurhead;// 遍历找到目标元素的前一个节点while(cur.next.x!o){curcur.next;}if(curnull){returnfalse;}// 处理尾节点删除if(cur.next.nextnull){cur.nextnull;tailcur;returntrue;}cur.nextcur.next.next;returntrue;}2删除指定索引元素remove(int index)功能删除指定索引位置的节点并返回被删除的元素。实现逻辑• 遍历到目标索引的前一个节点• 保存被删除节点的数值将前一个节点的next指向目标节点的下一个节点• 返回被删除的元素索引越界返回null。OverridepublicEremove(intindex){Nodecurhead;for(inti0;iindex;i){curcur.next;if(cur.nextnull){returnnull;}}Ex(E)cur.next.x;cur.nextcur.next.next;returnx;}3删除第一个元素removeFirst()功能删除链表第一个有效节点并返回该节点的数值。实现逻辑• 校验链表是否为空空则抛出异常• 保存第一个节点的数值• 将头节点的next指向第二个节点完成删除• 返回被删除的数值。OverridepublicEremoveFirst(){EheadElement(E)head.next.x;if(head.nextnull){thrownewNoSuchElementException(链表为空无法删除第一个元素);}head.nexthead.next.next;returnheadElement;}4删除最后一个元素removeLast()功能删除链表最后一个节点并返回该节点的数值。实现逻辑• 遍历到倒数第二个节点• 保存最后一个节点的数值• 将倒数第二个节点的next置空更新tail指针为倒数第二个节点• 返回被删除的数值链表为空返回null。OverridepublicEremoveLast(){Nodecurhead.next;if(curnull){returnnull;}while(cur.next.next!null){curcur.next;}ELastelement(E)cur.next.x;tailcur;cur.nextnull;returnLastelement;}5清空链表clear()功能删除链表所有有效节点清空数据。实现逻辑• 遍历链表将每个节点的数值置空• 最后将头节点的next置空链表恢复为空状态。Overridepublicvoidclear(){Nodecurhead.next;while(cur!null){cur.xnull;curcur.next;}head.nextnull;}3. 元素修改方法set(int index, Object o)功能修改指定索引位置节点的数值返回被替换的旧数值。实现逻辑• 遍历到目标索引对应的节点• 保存旧数值将节点的数值更新为新值• 索引越界返回null否则返回旧数值。OverridepublicObjectset(intindex,Objecto){Nodecurhead;for(inti0;iindex;i){curcur.next;if(cur.nextnull){System.out.println(索引越界);returnnull;}}EoldElement(E)cur.x;cur.xo;returnoldElement;}4. 元素查询方法1获取指定索引元素get(int index)功能返回指定索引位置节点的数值。实现逻辑• 遍历到目标索引对应的节点• 索引越界返回null否则返回节点数值。OverridepublicEget(intindex){Nodecurhead;for(inti0;iindex;i){curcur.next;if(cur.nextnull){System.out.println(索引越界);returnnull;}}Eelement(E)cur.x;returnelement;}2获取第一个元素getFirst()功能返回链表第一个有效节点的数值不删除。实现逻辑• 校验链表是否为空• 直接返回头节点后第一个节点的数值。OverridepublicEgetFirst(){if(head.nextnull){System.out.println(链表为空);returnnull;}Eelement(E)head.next.x;returnelement;}3获取最后一个元素getLast()功能返回链表最后一个节点的数值不删除。实现逻辑直接通过tail指针获取尾节点的数值。OverridepublicEgetLast(){return(E)tail.x;}4查找元素第一次出现的索引indexOf(Object o)功能遍历链表返回目标元素第一次出现的索引不存在返回-1。实现逻辑• 从第一个有效节点开始遍历计数索引• 找到匹配元素时返回当前计数遍历结束未找到返回-1。OverridepublicintindexOf(Objecto){intcount0;Nodecurhead.next;while(cur.x!o){curcur.next;count;}if(head.nextnull){return-1;}returncount;}5查找元素最后一次出现的索引lastIndexOf(Object o)功能遍历链表返回目标元素最后一次出现的索引不存在返回-1。实现逻辑• 遍历链表记录每次匹配元素的索引• 最终返回最后一次匹配的索引未匹配返回-1。OverridepublicintlastIndexOf(Objecto){intcount0;intflag0;Nodecurhead.next;while(cur.next!null){curcur.next;count;if(cur.xo){flagcount;}}if(head.nextnull||flag0){return-1;}returnflag;}5. 链表状态判断方法1判断链表是否为空isEmpty()功能判断链表是否包含有效节点。实现逻辑检查头节点的next是否为空为空则链表无有效节点返回true否则返回false。OverridepublicbooleanisEmpty(){if(head.nextnull){returntrue;}returnfalse;}2判断链表是否包含指定元素contains(Object o)功能判断目标元素是否存在于链表中。实现逻辑• 遍历链表匹配到目标元素返回true• 遍历结束未匹配返回false。Overridepublicbooleancontains(Objecto){Nodecurhead.next;while(cur.x!ocur.next!null){curcur.next;}if(cur.nextnull){returnfalse;}else{returntrue;}}3获取链表元素个数size()功能返回链表中有效节点的数量。实现逻辑• 从第一个有效节点开始遍历计数节点数量• 空链表返回0否则返回计数结果。Overridepublicintsize(){intcount1;Nodecurhead.next;if(curnull){return0;}while(cur.next!null){curcur.next;count;}returncount;}3.测试结果测试结果及部分代码如下所示publicstaticvoidmain(Stringargs[]){//初始让尾节点指向头节点tailhead;//创建测试类test test1newtestNode();for(inti0;i10;i){//创建一个新节点NodenewnodenewNodeInteger();newnode.xi;tail.nextnewnode;tailtail.next;}//头部插入test1.addFirst(String);//尾部插入test1.addLast(tail);//添加并查看是否成功if(test1.add(676)){System.out.println(添加元素676成功目前链表元素个数为test1.size());};//根据索引处插入元素test1.add(6,middle);System.out.println(目前链表元素个数为test1.size());//删除指定元素并查看是否成功if(test1.removefirstappear(tail)){System.out.println(删除元素tail成功目前链表元素个数为test1.size());}else{System.out.println(删除元素tail失败);}//删除指定索引的元素System.out.println(被删除的索引为7的元素为test1.remove(7)目前链表元素个数为test1.size());//删除并返回第一个元素System.out.println(删除的第一个元素为test1.removeFirst()目前链表元素个数为test1.size());//删除并返回最后一个元素System.out.println(删除的最后一个元素为test1.removeLast()目前链表元素个数为test1.size());//修改指定索引位置的元素System.out.println(修改元素test1.set(3,第四个元素)目前链表元素个数为test1.size());//获取指定索引位置的元素System.out.println(获取索引位置为3的元素为test1.get(3)目前链表元素个数为test1.size());//获取链表第一个元素(不删除)System.out.println(链表第一个元素为test1.getFirst()目前链表元素个数为test1.size());//获取链表最后一个元素(不删除)System.out.println(链表最后一个元素为test1.getLast()目前链表元素个数为test1.size());//查询指定元素在链表中第一次出现的索引test1.add(6,1);System.out.println(元素1在链表中第一次出现的索引为test1.indexOf(1)目前链表元素个数为test1.size());//查询指定元素在链表中最后一次出现的索引System.out.println(元素1在链表中最后一次出现的索引为test1.lastIndexOf(1)目前链表元素个数为test1.size());//判断链表是否为空if(!test1.isEmpty()){System.out.println(链表不为空);}else{System.out.println(链表为空);}//判断链表是否包含此元素if(test1.contains(234)){System.out.println(链表中包含此元素);}else{System.out.println(链表中不包含此元素);}//创建指针链表打印链表元素。Nodecurhead.next;while(cur!null){System.out.println(cur.x);curcur.next;}}4、总结通过手写链表的核心方法我们能更深入理解链表的底层逻辑链表的核心是节点的 “指针” 关联增删操作的本质是调整节点的next指向查询操作则需要遍历链表。相比于数组链表无需连续内存插入删除效率更高但查询效率较低需遍历。本次实现的链表包含了线性表的基本操作虽然代码中部分边界条件处理可进一步优化如索引越界的严格校验但核心逻辑符合基本的要求能帮助大家理解链表的核心思想。