Java数据结构之链表(动力节点之Java学院整理)
作者:mrr 时间:2022-08-29 16:40:18
单链表:
insertFirst:在表头插入一个新的链接点,时间复杂度为O(1)
deleteFirst:删除表头的链接点,时间复杂度为O(1)
find:查找包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N)
remove:删除包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N)
public class LinkedList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
public void insertFirst(Object obj){
Data data = new Data(obj);
data.next = first;
first = data;
}
public Object deleteFirst() throws Exception{
if(first == null)
throw new Exception("empty!");
Data temp = first;
first = first.next;
return temp.obj;
}
public Object find(Object obj) throws Exception{
if(first == null)
throw new Exception("LinkedList is empty!");
Data cur = first;
while(cur != null){
if(cur.obj.equals(obj)){
return cur.obj;
}
cur = cur.next;
}
return null;
}
public void remove(Object obj) throws Exception{
if(first == null)
throw new Exception("LinkedList is empty!");
if(first.obj.equals(obj)){
first = first.next;
}else{
Data pre = first;
Data cur = first.next;
while(cur != null){
if(cur.obj.equals(obj)){
pre.next = cur.next;
}
pre = cur;
cur = cur.next;
}
}
}
public boolean isEmpty(){
return (first == null);
}
public void display(){
if(first == null)
System.out.println("empty");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("\n");
}
public static void main(String[] args) throws Exception {
LinkedList ll = new LinkedList();
ll.insertFirst(4);
ll.insertFirst(3);
ll.insertFirst(2);
ll.insertFirst(1);
ll.display();
ll.deleteFirst();
ll.display();
ll.remove(3);
ll.display();
System.out.println(ll.find(1));
System.out.println(ll.find(4));
}
}
1 -> 2 -> 3 -> 4 ->
2 -> 3 -> 4 ->
2 -> 4 ->
null
4
双端链表(不是双向链表):
与单向链表的不同之处在保存有对最后一个链接点的引用(last)
insertFirst:在表头插入一个新的链接点,时间复杂度O(1)
insertLast:在表尾插入一个新的链接点,时间复杂度O(1)
deleteFirst:删除表头的链接点,时间复杂度O(1)
deleteLast::删除表尾的链接点,由于只保存了表尾的链接点,而没有保存表尾的前一个链接点(这里就体现出双向链表的优势了),所以在删除表尾链接点时需要遍历以找到表尾链接点的前一个链接点,需查找N-1次,也就是O(N)
有了这几个方法就可以用双端链表来实现一个队列了
public class FirstLastList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
private Data last = null;
public void insertFirst(Object obj){
Data data = new Data(obj);
if(first == null)
last = data;
data.next = first;
first = data;
}
public void insertLast(Object obj){
Data data = new Data(obj);
if(first == null){
first = data;
}else{
last.next = data;
}
last = data;
}
public Object deleteFirst() throws Exception{
if(first == null)
throw new Exception("empty");
Data temp = first;
if(first.next == null)
last = null;
first = first.next;
return temp.obj;
}
public void deleteLast() throws Exception{
if(first == null)
throw new Exception("empty");
if(first.next == null){
first = null;
last = null;
}else{
Data temp = first;
while(temp.next != null){
if(temp.next == last){
last = temp;
last.next = null;
break;
}
temp = temp.next;
}
}
}
public void display(){
if(first == null)
System.out.println("empty");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("\n");
}
public static void main(String[] args) throws Exception {
FirstLastList fll = new FirstLastList();
fll.insertFirst(2);
fll.insertFirst(1);
fll.display();
fll.insertLast(3);
fll.display();
fll.deleteFirst();
fll.display();
fll.deleteLast();
fll.display();
}
}
1 -> 2 ->
1 -> 2 -> 3 ->
2 -> 3 ->
2 ->
有序链表:
链表中的数据按从小到大排列
public class SortedList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
public void insert(Object obj){
Data data = new Data(obj);
Data pre = null;
Data cur = first;
while(cur != null && (Integer.valueOf(data.obj.toString())
.intValue() > Integer.valueOf(cur.obj.toString())
.intValue())){
pre = cur;
cur = cur.next;
}
if(pre == null)
first = data;
else
pre.next = data;
data.next = cur;
}
public Object deleteFirst() throws Exception{
if(first == null)
throw new Exception("empty!");
Data temp = first;
first = first.next;
return temp.obj;
}
public void display(){
if(first == null)
System.out.println("empty");
System.out.print("first -> last : ");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("\n");
}
public static void main(String[] args) throws Exception{
SortedList sl = new SortedList();
sl.insert(80);
sl.insert(2);
sl.insert(100);
sl.display();
System.out.println(sl.deleteFirst());
sl.insert(33);
sl.display();
sl.insert(99);
sl.display();
}
}
first -> last : 2 -> 80 -> 100 ->
2
first -> last : 33 -> 80 -> 100 ->
first -> last : 33 -> 80 -> 99 -> 100 ->
表的插入和删除平均需要比较N/2次,即O(N),但是获取最小数据项只需O(1),因为其始终处于表头,对频繁操作最小数据项的应用,可以考虑使用有序链表实现,如:优先级队列和数组相比,链表的优势在于长度不受限制,并且在进行插入和删除操作时,不需要移动数据项,故尽管某些操作的时间复杂度与数组想同,实际效率上还是比数组要高很多。劣势在于随机访问,无法像数组那样直接通过下标找到特定的数据项 。
以上所述是小编给大家介绍的Java数据结构之链表(动力节点之Java学院整理)网站的支持!
标签:java,数据结构,链表
0
投稿
猜你喜欢
android TextView设置中文字体加粗实现方法
2023-08-06 02:32:03
myEclipse配置jdk1.7教程
2022-07-21 11:25:35
C#实现系统休眠或静止休眠的方法
2023-12-19 01:55:29
java必学必会之线程(2)
2023-11-09 10:22:35
java文字转语音播报功能的实现方法
2022-05-08 18:44:41
聊聊java中引用数据类型有哪些
2022-01-10 11:59:10
Java集合TreeSet用法详解
2023-11-10 22:53:34
Swing常用组件之多行文本区JTextArea
2023-11-08 14:16:49
Java对象不使用时赋值null的意义详解
2023-11-25 01:46:20
如何将maven源改为国内阿里云镜像
2023-07-25 13:47:33
C#识别出图片里的数字和字母
2023-04-12 08:21:41
C#实现的json序列化和反序列化代码实例
2022-04-05 22:24:08
详解Java中的Vector
2023-06-05 01:40:49
IDEA离线安装maven helper插件的图文教程
2023-11-28 16:00:24
AOP之事务管理<aop:advisor>的两种配置方式
2023-11-24 22:55:06
以Java代码为例讲解设计模式中的简单工厂模式
2023-02-09 15:14:17
SpringBoot 集成 Druid过程解析
2023-02-25 12:07:59
jvm运行原理以及类加载器实例详解
2023-10-23 18:39:03
Java Socket编程(五) 简单的WEB服务器
2023-05-23 01:00:04
Android Studio多渠道打包的配置方法
2023-06-15 23:19:48