关键词:
链表有初始化、插入元素、删除元素、查找元素等方法。在创建链表的过程中,最关键的是搞清楚链表的几个关键数据构成:链表由一个个节点互相串联构成,节点作为一个基础的对象,可由类Node(随便取个名字都行)来声明。节点中包含三个值,key(int)用于存储数据值的大小、prev(Node)用作指针指向上一个节点、next(Node)用作指针指向下一个节点。
本文实现的双向链表,在初始化时,头节点nil的prev和next指针均指向自己。而在插入元素时,则比较讲究,可以参考下图:
实现代码如下:
Main.java
public class Main
public static void main(String[] args)
BidirectionalLinkedList LinkedList = new BidirectionalLinkedList();
LinkedList.insert(1);//链表添加元素
LinkedList.insert(3);
LinkedList.insert(9);
LinkedList.insert(8);
LinkedList.insert(4);
LinkedList.insert(7);
LinkedList.insert(2);
LinkedList.show();//实现链表的遍历
// //实现链表的搜索
// BidirectionalLinkedList.Node cur = LinkedList.listSearch(2);
// System.out.println("查找元素为:" + cur.key);
//实现链表的删除节点
System.out.println("删除第一个元素...");
LinkedList.deleteFirst();
LinkedList.show();
System.out.println("删除最后一个元素...");
LinkedList.deleteLast();
LinkedList.show();
System.out.println("删除元素9...");
LinkedList.deleteKey(9);
LinkedList.show();
public class BidirectionalLinkedList
class Node//节点的定义
int key=Integer.MIN_VALUE;
Node prev, next;
Node nil = new Node();
//链表初始化
BidirectionalLinkedList()
this.nil.next = this.nil;
this.nil.prev = this.nil;
//链表的遍历
public void show()
BidirectionalLinkedList.Node head_nil = this.nil;
System.out.println("链表中的元素为:");
while(this.nil.next != head_nil)
System.out.print(this.nil.next.key + " ");
this.nil = this.nil.next;
System.out.println("");
this.nil = head_nil;//遍历完要把头指针指回来
//插入元素
public void insert(int key)
Node x = new Node();
x.key = key;
//在头节点后添加元素
x.next = nil.next;
nil.next.prev = x;
nil.next = x;
x.prev = nil;
public Node listSearch(int key)
Node cur = new Node();
cur = nil.next;//从头节点后面的元素开始访问
while(cur!=nil && cur.key!=key)
cur = cur.next;
return cur;
public void deleteNode(Node t)
if(t==nil)return;//t未为头节点时不做处理
t.prev.next = t.next;
t.next.prev = t.prev;
public void deleteFirst()
deleteNode(nil.next);
public void deleteLast()
deleteNode(nil.prev);
public void deleteKey(int key)
//删除搜索到的节点
deleteNode(listSearch(key));
代码输出结果为:
链表中的元素为:
2 7 4 8 9 3 1
删除第一个元素...
链表中的元素为:
7 4 8 9 3 1
删除最后一个元素...
链表中的元素为:
7 4 8 9 3
删除元素9...
链表中的元素为:
7 4 8 3
作于:
2021-11-8
14:41
挑战程序设计竞赛(算法和数据结构)——4.5java中对应c++stl的数据结构类
挑战程序设计竞赛(算法和数据结构)——3.6希尔排序的java实现(代码片段)
题目&思路:代码:importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;publicclassShellSortpublicstaticlongcnt;publicstaticintA[]=newint[1000000];publicstaticintn;publ 查看详情
挑战程序设计竞赛(算法和数据结构)——7.7最小成本排序的java实现(代码片段)
题目&思路:代码:importjava.util.*;publicclassMinimumCostSortpublicstaticfinalintMAX=1000;publicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();in 查看详情
挑战程序设计竞赛(算法和数据结构)——17.4最大正方形的java实现(代码片段)
题目&思路:代码:importjava.util.Scanner;publicclassLargestSquarepublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intH=cin.nextInt();intW=cin.nextInt();intmap[] 查看详情
挑战程序设计竞赛(算法和数据结构)——5.5迭代器和二分查找的java实现(代码片段)
迭代器代码:importjava.util.Arrays;importjava.util.Iterator;publicclassIteratorDemopublicstaticvoidmain(String[]args)int[]arr=newint[]1,2,3,4,5,6,7,8,9,8,2,6,5,7,1,3,4,5,6;Iterator<Integer 查看详情
挑战程序设计竞赛(算法和数据结构)——5.4散列法习题java代码实现(代码片段)
题目:散列法相关的代码可以参考之前一篇博文https://blog.csdn.net/weixin_42887138/article/details/121254659importjava.lang.ref.PhantomReference;importjava.util.Scanner;publicclass_5_4publicstaticvoidmain(String[]arg 查看详情
挑战程序设计竞赛(算法和数据结构)——4.6数据结构的应用——计算面积java代码实现(代码片段)
题目:代码及实现思路如下:importjava.io.BufferedInputStream;importjava.util.Scanner;importjava.util.Stack;importjava.util.Vector;publicclass_4_6publicstaticvoidmain(String[]args)/*设计两个栈,S1和S 查看详情
挑战程序设计竞赛(算法和数据结构)——4.3队列习题的java实现(代码片段)
题目:基本思路:将任务定义为一个包含名称和时间的Task类,定义一个Task类型的队列,并循环下列算法:用时间sum_time来记录处理情况,只要队列不为空,就不断执行当处理一个队头任务时,首先... 查看详情
挑战程序设计竞赛(算法和数据结构)——分割(下)&快速排序的java实现(代码片段)
在《挑战程序设计竞赛(算法和数据结构)——7.2分割(上)JAVA实现》中实现了将任一数组的元素以最后一个元素为界,小的排在前,大的排在后的功能,参照以下链接:https://blog.csdn.net/weixin_42887... 查看详情
挑战程序设计竞赛(算法和数据结构)——16.13线段相交问题(曼哈顿算法)的java实现(代码片段)
题目与思路:代码:importjava.util.*;publicclassManhattanGeometrypublicstaticclassEpElementprivateGraghBasic.PointP;privateStringdirection;//left,right,bottom,topprivateintid;EpElement()EpElement(GraghBasic.PointP,Stringdirection,intid)this.P=P;this.direction=direction;this... 查看详情
挑战程序设计竞赛(算法和数据结构)——16.12凸包(安德鲁算法)的java实现(代码片段)
题目与思路:代码:importjava.util.*;//数据结果套数据结构时,需要一层一层初始化publicclassConvexHullpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();Vector<GraghBasic.Point>S=newVector<GraghBasic.Poi... 查看详情
挑战程序设计竞赛(算法和数据结构)——13.3单源最短路径(dijkstra算法)的java实现(代码片段)
题目:代码:importjava.io.BufferedInputStream;importjava.io.BufferedReader;importjava.util.Scanner;publicclassSingleSourceShortestPathpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();//初始化邻接矩阵MintM[][]... 查看详情
挑战程序设计竞赛(算法和数据结构)——12.2图的表示java实现(代码片段)
题目:importjava.util.Scanner;publicclassGraphImplementpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();//建立图的邻接矩阵intM[][]=newint[n][n];for(inti=0;i<n;i++)intid=cin.nextInt();intdegree=cin.nextInt();for(i... 查看详情
挑战程序设计竞赛(算法和数据结构)——7.2分割(上)java实现(代码片段)
题目:思路:示例1:示例2:代码如下:importjava.io.BufferedInputStream;importjava.util.Scanner;publicclassPartitionpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();int[]A=newint[n];for(inti=... 查看详情
挑战程序设计竞赛(算法和数据结构)——12.5连通分量的java实现(代码片段)
题目:讲解:注意:定义了一个Vector类型的数组,不仅需要初始化Vector类型的数组,还需初始化每一个Vector类型的容器。否则会出现以下异常:Exceptioninthread“main”java.lang.NullPointerException:Cannotinvoke“java.uti... 查看详情
挑战程序设计竞赛(算法和数据结构)——7.1归并排序java实现(代码片段)
归并排序思路:代码如下:importjava.io.BufferedInputStream;importjava.util.Scanner;publicclassMergeSortpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();int[]S=newint[n];for(inti=0;i<n;i++)S[i... 查看详情
挑战程序设计竞赛(算法和数据结构)——15.3关节点的java实现(代码片段)
题目:代码:importjava.util.ArrayList;importjava.util.HashSet;importjava.util.Scanner;importjava.util.Set;publicclassArticulationPointpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intN=cin.nextInt();intm=cin.nextInt();ArrayList<Integer>G[]=n... 查看详情
挑战程序设计竞赛(算法和数据结构)——15.3关节点的java实现(代码片段)
题目:代码:importjava.util.ArrayList;importjava.util.HashSet;importjava.util.Scanner;importjava.util.Set;publicclassArticulationPointpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intN=cin.nextInt();intm=cin.nextInt();ArrayList<Integer>G[]=n... 查看详情