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
接下来这是三个功能我放在一起演示：
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();
运行结果：注意头插法输出结果是倒序的！
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()
运行结果：尾插法输出结果是正序的！
【数据结构与算法】LinkedList与链表(上)
分类专栏： 【数据结构与算法】 文章标签： 数据结构 算法 java
8 篇文章 0 订阅
✨hello，进来的小伙伴们，你们好耶！✨
🍊🍊系列专栏：【数据结构与算法】
🌯🌯本篇内容：初始LinkedList与链表，链表的概念，结构，基本实现，详细全面介绍！
🍼🍼作者简介：一名大三在读的科班Java编程小白，我很平凡，学会努力！
🍬🍬码云存放仓库gitee：https://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、链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
即我们可以通俗的理解为比如火车的车厢，没有给这些车厢连接起来，他们只是普通的车厢，互相之间没有任何联系，通过任意一节车厢我们无法确定下一节车厢，那么给他们连接起来组成一列火车的车厢，那么就可以是看做一种链表的结构。
那么在实际的应用中，链表的结构也是多样的。
1.带头或者不带头。
2.单向或双向。
3.循环或非循环。
那么这些组合起来就有8种链表结构，那么我们需要重点掌握的就2种：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表 。
2、链表的实现
接下来我将模拟链表的功能实现，借助我们的idea工具来演示！
具体的实现细节都在我的代码注释中标明，大家有不懂的可以评论区或者私信我都可以的！
1.首先我们新建一个包LinkedList。
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. }
看一下结果：说明我们链表创建成功了！
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. }
运行结果：
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. }
运行结果：
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。
接下来这是三个功能我放在一起演示：
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();
运行结果：注意头插法输出结果是倒序的！
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()
运行结果：尾插法输出结果是正序的！
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，期待你的关注与三连！
