开发者社区> IT辰柒_Java> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

arraylist与顺序表

简介: arrayl与顺序表
+关注继续查看

6、查找是否包含关键字key是否在单链表当中

       public boolean contains(int key){

           ListNode cur = this.head;

           while(cur!=null){

               if(cur.val == key){

                   return true;

               }

               cur = cur.next;

           }

           return false;

       }

运行结果:这里我给的测试用例是12,所以返回TRUE。

68b843c9d46f4ac5838d880a526dfe7a.png

68b843c9d46f4ac5838d880a526dfe7a.png

接下来这是三个功能我放在一起演示:

7.头插法

       public void addFirst(int data){

           //当你在链表当中插入一个数据的时候 一点要记住 先去绑定后面的节点

           //比起顺序表的好处就是 1:插入数的时候不用挪动元素 2:只需要修改指向即可。时间复杂度是O(1)

           ListNode node = new ListNode(data);

           node.next = head;

           head = node;

       }

主函数代码:

           mySingleList.addFirst(12);//头插法

           mySingleList.addFirst(23);

           mySingleList.addFirst(34);

           mySingleList.addFirst(45);

           mySingleList.addFirst(56);

           mySingleList.display();

运行结果:注意头插法输出结果是倒序的!

f419d92760d04bde8ef12a9e16ef03db.png

8.尾插法

    public void addLast(int data){

           ListNode node = new ListNode(data);

           ListNode cur = this.head;

           if(cur == null){

               this.head = node;

           }else{

               while(cur.next!= null){

                   cur = cur.next;

               }

               //走到这个时候已经找到尾巴了

               cur.next = node;

           }

       }

主函数代码:

             mySingleList.addLast(12);

             mySingleList.addLast(23);

             mySingleList.addLast(34);

             mySingleList.addLast(45);

             mySingleList.addLast(56);

             mySingleList.display()

运行结果:尾插法输出结果是正序的!

ff7152c1f78e45fa8a956b5a6ad10c40.png

【数据结构与算法】LinkedList与链表(上)

image

辰柒_ image 于 2022-09-19 19:49:21 发布 image 320 image

分类专栏: 【数据结构与算法】 文章标签: 数据结构 算法 java

编辑 版权

image

8 篇文章 0 订阅

✨hello,进来的小伙伴们,你们好耶!✨

🍊🍊系列专栏:【数据结构与算法】

🌯🌯本篇内容:初始LinkedList与链表,链表的概念,结构,基本实现,详细全面介绍!

🍼🍼作者简介:一名大三在读的科班Java编程小白,我很平凡,学会努力!

🍬🍬码云存放仓库giteehttps://gitee.com/king-zhou-of-java/java-se.git

一、ArrayList的缺陷

通过上篇博客的学习,我们可以通过ArrayList的源码了解到,ArrayList底层使用数组来存储元素。

1. public class ArrayList<E> extends AbstractList<E>
2.     implements List<E>, RandomAccess, Cloneable, java.io.Serializable
3. {
4.  // ...
5.  // 默认容量是10
6.   private static final int DEFAULT_CAPACITY = 10;
7.   //...
8.  
9.   // 数组:用来存储元素
10.   transient Object[] elementData; // non-private to simplify nested class access
11.  
12.   // 有效元素个数
13.   private int size;
14.   public ArrayList(int initialCapacity) {
15.     if (initialCapacity > 0) {
16.       this.elementData = new Object[initialCapacity];
17.    } else if (initialCapacity == 0) {
18.       this.elementData = EMPTY_ELEMENTDATA;
19.    } else {
20.       throw new IllegalArgumentException("Illegal Capacity: "+
21.                        initialCapacity);
22.    }
23.  }

因为其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低。因此:java集合中又引入了LinkedList,即链表结构。

二、链表

1、链表的概念及结构

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

即我们可以通俗的理解为比如火车的车厢,没有给这些车厢连接起来,他们只是普通的车厢,互相之间没有任何联系,通过任意一节车厢我们无法确定下一节车厢,那么给他们连接起来组成一列火车的车厢,那么就可以是看做一种链表的结构。

image

那么在实际的应用中,链表的结构也是多样的。

1.带头或者不带头。

2.单向或双向。

3.循环或非循环。

那么这些组合起来就有8种链表结构,那么我们需要重点掌握的就2种:

无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

image

无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表 。

image

2、链表的实现

接下来我将模拟链表的功能实现,借助我们的idea工具来演示!

具体的实现细节都在我的代码注释中标明,大家有不懂的可以评论区或者私信我都可以的!

1.首先我们新建一个包LinkedList。

image

 2.然后我们定义我们的实现类MySingleList,在这个类当中定义一个节点内部类ListNode,当然这个类也可以是静态的都没有什么问题,在这个类当中呢,我们定义成员变量val,和节点next。

1. static class ListNode {
2. public int val;
3. public ListNode next;
4. 
5. public ListNode(int val) {
6. this.val = val;
7. 
8.         }
9.     }

3、OK那么接下来我们先创建我们的链表。

1. public ListNode head;//不初始化了 默认就是null
2. 
3. public void createList() {//最简单的方式 穷举
4.         ListNode listNode1 = new ListNode(12);
5.         ListNode listNode2 = new ListNode(23);
6.         ListNode listNode3 = new ListNode(34);
7.         ListNode listNode4 = new ListNode(45);
8.         ListNode listNode5 = new ListNode(56);
9.         listNode1.next = listNode2;//当前节点存储下一个元素的地址
10.         listNode2.next = listNode3;
11.         listNode3.next = listNode4;
12.         listNode4.next = listNode5;
13. this.head = listNode1;
14.     }

看一下结果:说明我们链表创建成功了!

image

 4.接下来我们打印这个单链表。

1. public void display() {
2.         ListNode cur = this.head;//head不变 让我们的头结点不变 cur去变
3. while (cur != null) {
4. /**
5.              为什么是判断cur不等于空 而不是判断cur.next不为空
6.             我们可以打印出最后一个元素 否则提前判断 不能遍历到最后一个元素
7.             */
8.             System.out.print(cur.val+" ");
9.             cur = cur.next;
10.         }
11.     }

运行结果:

image

 5.计算单链表的长度。

1. public int size(){
2.         ListNode cur = this.head;
3. int count =0;
4. while(cur!=null){//可不敢写成cur.next!=null 如果链表为空的话 那么cur.next就会发生空指针异常 报错
5.             count++;
6.             cur = cur.next;
7.         }
8. return count;
9.     }

运行结果:

image

6、查找是否包含关键字key是否在单链表当中

1. public boolean contains(int key){
2.         ListNode cur = this.head;
3. while(cur!=null){
4. if(cur.val == key){
5. return true;
6.             }
7.             cur = cur.next;
8.         }
9. return false;
10.     }

运行结果:这里我给的测试用例是12,所以返回TRUE。

image

接下来这是三个功能我放在一起演示:

 7.头插法

1. public void addFirst(int data){
2. //当你在链表当中插入一个数据的时候 一点要记住 先去绑定后面的节点
3. //比起顺序表的好处就是 1:插入数的时候不用挪动元素 2:只需要修改指向即可。时间复杂度是O(1)
4.         ListNode node = new ListNode(data);
5.         node.next = head;
6.         head = node;
7.     }

主函数代码:

1.         mySingleList.addFirst(12);//头插法
2.         mySingleList.addFirst(23);
3.         mySingleList.addFirst(34);
4.         mySingleList.addFirst(45);
5.         mySingleList.addFirst(56);
6.         mySingleList.display();

运行结果:注意头插法输出结果是倒序的!

image

8.尾插法

1. public void addLast(int data){
2.         ListNode node = new ListNode(data);
3.         ListNode cur = this.head;
4. if(cur == null){
5. this.head = node;
6.         }else{
7. while(cur.next!= null){
8.                 cur = cur.next;
9.             }
10. //走到这个时候已经找到尾巴了
11.             cur.next = node;
12.         }
13.     }

主函数代码:

1.           mySingleList.addLast(12);
2.           mySingleList.addLast(23);
3.           mySingleList.addLast(34);
4.           mySingleList.addLast(45);
5.           mySingleList.addLast(56);
6.           mySingleList.display()

运行结果:尾插法输出结果是正序的!

image

9.任意位置插入

1. public void addIndex(int index,int data){
2. if(index<0 || index>size()){
3.             System.out.println("index位置不合法!");
4. throw new IndexWrongFulException("index位置不合法!");
5.         }
6. if(index == 0){//相当于头插法
7. addFirst(data);
8. return;
9.         }
10. if(index == size()) {//相当于尾插法
11. addLast(data);
12. return;
13.         }
14. //1.先走index-1步 找到cur
15.         ListNode cur = findIndexSubOne(index);
16.         ListNode node = new ListNode(data);
17. //2.修改指向
18.         node.next = cur.next;
19.         cur.next = node;
20.     }
21. private ListNode findIndexSubOne(int index){
22. //定义成private本来就是想只提供给我这个任意位置的插入的函数使用
23. // 不想让类外的函数等访问
24.         ListNode cur = this.head;
25. while(index-1!=0){
26.             cur = cur.next;
27.             index--;
28.         }
29. return cur;
30.     }

主函数代码:

1.         mySingleList.addIndex(3,666);//在任意位置插入数据
2.         System.out.println("任意位置插入数据:");
3.         mySingleList.display();
4.         mySingleList.remove(34);
5.         System.out.println("任意位置插入数据后:");
6.         mySingleList.display();
7.         System.out.println();

好了,那么由于演示的功能较多,我们一篇博客就不长篇大段的去阐述了,为了我们阅读的体验感和掌握知识的程度,我们下篇博客继续学习LinkedList,期待你的关注与三连!

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java ArrayList类
Java ArrayList类
10 0
ArrayList 深度学习
ArrayList 深度学习
42 0
集合之ArrayList
正则表达式有固定的规律的格式,匹配字符串 1.用于字符串格式的校验 2.按照某种字符串的格式 进行拆分 替换 3.在比较大段的字符串中寻找 符合某种格式的子字符串 有一些匹配格式的符号写法 [abc] [^abc] [a-zA-Z] [a-z[^bc]] . \d \D \s \S \w \W 有一些用来匹配出现次数 ? 0-1 *0-n +1-n {n} {n,} {n,m} Pattern p = Pattern.compile("regex"); Matche
23 0
聊聊ArrayList的问题
聊聊ArrayList的问题
48 0
asList和ArrayList不得不说的故事
asList和ArrayList不得不说的故事
24 0
Java常见面试题:ArrayList实现原理
类集里面使用最多的就是ArrayList,使用ArrayList之前往往需要一些约定。ArrayList线性复杂度是1,可以直接通过索引进行访问。实际上这个过程和数组是非常相似的。
4435 0
+关注
IT辰柒_Java
攀登者!
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载