devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

五分钟“手撕”链表

作者：菜鸟追梦旅行 | 2024-06-02 06:59:48

赞

踩

五分钟“手撕”链表

为了提高大家的学习效率，我把代码放开头，供查阅。 

目录

一、链表的实现代码

二、什么是链表

三、链表的分类

四、链表的常见操作

插入

删除 

五、Java自带的LinkedList 

 两个构造方法

 一些常用方法

六、LinkedList的遍历

七、ArrayList和LinkedList的区别  

一、链表的实现代码

  1. //无头单向链表
  2. package demo1;
  3. public class MySingleLinkedList{
  4.     class ListNode{
  5.         public int var;
  6.         public ListNode next;
  7.         public int val;
  8.  
  9.         public ListNode(int var) {
  10.             this.var = var;
  11.         }
  12.     }
  13.     ListNode head;
  14.     public void creat(){
  15.         ListNode node1=new ListNode(1);
  16.         ListNode node2=new ListNode(1);
  17.         ListNode node3=new ListNode(1);
  18.         ListNode node4=new ListNode(1);
  19.  
  20.         node1.next=node2;
  21.         node2.next=node3;
  22.         node3.next=node4;
  23.         head=node1;
  24.     }
  25.     //头插法
  26.     public void addFirst(int data) {
  27.         ListNode node=new ListNode(data);
  28.         node.next=head;
  29.         head=node;
  30.     }
  31.     //尾插法
  32.     public void addLast(int data) {
  33.         ListNode node=new ListNode(data);
  34.         if(head==null){
  35.             head=node;
  36.             return;
  37.         }
  38.         ListNode cur=head;
  39.         while (cur.next!=null){
  40.             cur=cur.next;
  41.         }cur.next=node;
  42.     }
  43.  
  44.     private void IndexCheck(int index)throws IndexNotLegal {
  45.         if(index<0||index>size()){
  46.             throw new IndexNotLegal("index位置不合法");
  47.         }
  48.     }
  49.     //任意位置插入,第一个数据节点为0号下标
  50.     public void addIndex(int index, int data){
  51.         try {
  52.             IndexCheck(index);
  53.         }catch (IndexNotLegal e){
  54.             e.printStackTrace();
  55.             return;
  56.         }
  57.         ListNode node=new ListNode(data);
  58.         ListNode cur=head;
  59.         if(index==0){
  60.             addFirst(data);
  61.             return;
  62.         }if(index==size()){
  63.             addLast(data);
  64.             return;
  65.         }
  66.         //注意这里是index-1
  67.         for (int i = 0; i < index-1; i++) {
  68.             cur= cur.next;
  69.         }
  70.         node.next=cur.next;
  71.         cur.next=node;
  72.     }
  73.     //查找是否包含关键字key是否在单链表当中
  74.     public boolean contains(int key) {
  75.         ListNode cur=head;
  76.         while (cur!=null){
  77.             if(cur.var==key){
  78.                 return true;
  79.             }cur=cur.next;
  80.         }return false;
  81.     }
  82.     //删除第一次出现关键字为key的节点
  83.     public void remove(int key) {
  84.         if(head.var==key){
  85.             head=head.next;
  86.             return;
  87.         }if(head==null){
  88.             return;
  89.         }
  90.         ListNode cur=head;
  91.         while (cur.next!=null){
  92.             if(cur.next.var==key){
  93.                 cur.next=cur.next.next;
  94.                 return;
  95.             }cur=cur.next;
  96.         }
  97.     }
  98.     //删除所有出现的key节点
  99.     public void removeAllKey(int key) {
  100.         if(head==null){
  101.             return;
  102.         }ListNode prev=head;
  103.         ListNode cur=head.next;
  104.         while (cur!=null){
  105.             if(cur.var==key){
  106.                 prev.next= cur.next;
  107.                 //这里不能写prev=cur
  108.                 cur= cur.next;
  109.             }else {
  110.                 prev=cur;
  111.                 cur= cur.next;
  112.             }
  113.             if(head.var==key){
  114.                 head=head.next;
  115.             }
  116.         }
  117.  
  118.     }
  119.     //得到单链表的长度
  120.     public int size() {
  121.         ListNode cur=head;
  122.         int count=0;
  123.         while (cur!=null){
  124.             count++;
  125.             cur=cur.next;
  126.         }return count;
  127.     }
  128.     //打印链表
  129.     public void display() {
  130.         ListNode cur=head;
  131.         for (int i = 0; i < size(); i++) {
  132.             System.out.print(cur.var+" ");
  133.             cur=cur.next;
  134.         }
  135.         System.out.println();
  136.     }
  137.     //清除链表
  138.     public void clear() {
  139.         head=null;
  140.     }
  141. }
  142.  
  143. public class IndexNotLegal extends RuntimeException {
  144.     public IndexNotLegal(){
  145.  
  146.     }public IndexNotLegal(String s){
  147.         super(s);
  148.     }
  149. }
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161. package demo2;
  162. // 无头双向链表
  163. public class MyLinkedList {
  164.  
  165.     class ListNode {
  166.         public int var;
  167.         ListNode prev;
  168.         ListNode next;
  169.  
  170.         public ListNode(int var) {
  171.             this.var = var;
  172.         }
  173.     }
  174.  
  175.     ListNode head;
  176.     ListNode last;
  177.  
  178.     //头插法
  179.     public void addFirst(int data) {
  180.         ListNode node = new ListNode(data);
  181.         if (head == null) {
  182.             head = last = node;
  183.             return;
  184.         }
  185.         node.next = head;
  186.         head.prev = node;
  187.         head = node;
  188.     }
  189.  
  190.     //尾插法
  191.     public void addLast(int data) {
  192.         ListNode node = new ListNode(data);
  193.         if (head == null) {
  194.             head = last = node;
  195.             return;
  196.         }
  197.         last.next = node;
  198.         node.prev = last;
  199.         last = node;
  200.     }
  201.  
  202.     private void indexCheck(int index) throws IndexNotLegal {
  203.         if (index < 0 || index > size()) {
  204.             throw new IndexNotLegal("index位置不合法");
  205.         }
  206.     }
  207.  
  208.     private ListNode findIndexCur(int index) {
  209.         ListNode cur = head;
  210.         while (index != 0) {
  211.             cur = cur.next;
  212.             index--;
  213.         }
  214.         return cur;
  215.     }
  216.  
  217.     //任意位置插入,第一个数据节点为0号下标
  218.     public void addIndex(int index, int data) {
  219.         try {
  220.             indexCheck(index);
  221.         } catch (IndexNotLegal e) {
  222.             e.printStackTrace();
  223.         }
  224.  
  225.         if (index == 0) {
  226.             addFirst(data);
  227.             return;
  228.         }
  229.         if (index == size()) {
  230.             addLast(data);
  231.             return;
  232.         }
  233.         ListNode node = new ListNode(data);
  234.         ListNode cur = findIndexCur(index);
  235.         //先把node插进去，再调整node的前一个，最后再调cur，因为需要cur来调整
  236.         node.next=cur;
  237.         cur.prev.next=node;
  238.         node.prev=cur.prev;
  239.         cur.prev=node;
  240.  
  241.  
  242.     }
  243.  
  244.     //查找是否包含关键字key是否在单链表当中
  245.     public boolean contains(int key) {
  246.         ListNode cur = head;
  247.         while (cur != null) {
  248.             if (cur.var == key) {
  249.                 return true;
  250.             }
  251.             cur = cur.next;
  252.         }
  253.         return false;
  254.     }
  255.  
  256.     //删除第一次出现关键字为key的节点
  257.     public void remove(int key) {
  258.         ListNode cur = head;
  259.         while (cur != null) {
  260.             if (cur.var == key) {
  261.                 //头节点
  262.                 if (head.var == key) {
  263.                     head.next.prev = null;
  264.                     head = head.next;
  265.                     return;
  266.                 }
  267.                 //尾巴节点
  268.                 if (last.var == key) {
  269.                     last.prev.next = null;
  270.                     last = last.prev;
  271.                     return;
  272.                 }
  273.                 cur.next.prev = cur.prev;
  274.                 cur.prev.next = cur.next;
  275.                 return;
  276.             }
  277.             cur = cur.next;
  278.         }
  279.     }
  280.  
  281.     //删除所有值为key的节点
  282.     public void removeAllKey(int key) {
  283.         ListNode cur = head;
  284.         while (cur != null) {
  285.             if (cur.var == key) {
  286.                 //头节点
  287.                 if (head.var == key) {
  288.                     head.next.prev = null;
  289.                     head = head.next;
  290.                     return;
  291.                 }
  292.                 //尾巴节点
  293.                 if (last.var == key) {
  294.                     last.prev.next = null;
  295.                     last = last.prev;
  296.                     return;
  297.                 }
  298.                 cur.next.prev = cur.prev;
  299.                 cur.prev.next = cur.next;
  300.             }
  301.             cur = cur.next;
  302.         }
  303.     }
  304.  
  305.  
  306.  
  307.     //得到单链表的长度
  308.     public int size() {
  309.         int count = 0;
  310.         ListNode cur = head;
  311.         while (cur != null) {
  312.             cur = cur.next;
  313.             count++;
  314.         }
  315.         return count;
  316.     }
  317.  
  318.     public void display() {
  319.         ListNode cur = head;
  320.         for (int i = 0; i < size(); i++) {
  321.             System.out.print(cur.var + " ");
  322.             cur = cur.next;
  323.         }
  324.         System.out.println();
  325.     }
  326.  
  327.     public void clear() {
  328.         head = last = null;
  329.     }
  330. }
  331.  
  332.  
  333. package demo2;
  334.  
  335. public class IndexNotLegal extends RuntimeException{
  336.     public IndexNotLegal(){
  337.  
  338.     }public IndexNotLegal(String s){
  339.         super(s);
  340.     }
  341. }

二、什么是链表

简单来说，像链子一样的数据结构。像火车一节一节车厢一样，每个元素是独立的个体（内部类）。 并且他们在空间里是分散的。 

 

为什么分散的还可以找到下一个呢？

答：一个节点里面装着两种东西，一个是值，一个的下一个的地址，这样根据下一个的地址就可以找到下一个了。 

三、链表的分类

常见的链表有三种，但是我这里只介绍两种：无头单链，无头双链。剩下的一种之后再补充。

单链和双链的区别？

答： 一个节点都是一个类。单链装的是值和下个节点；双链装的是值和上个节点和下个节点

四、链表的常见操作

插入

怎么插入元素？在链表中很简单！ 

单链：p下个节点改成n1，n0下个节点改为p。

双链： p下个节点改为n1，n0下个节点改为p（先把p插进去，成一个逆时针），p上个节点改为n0，n1的上个节点改为p（修改原来的两点节点）

注意！还需要考虑一些特殊情况，具体请看代码的实现！

删除 

在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。 

单链：n0的下个节点指向n1。

双链：n0下个节点改为n1，n1上个节点改为n0 。

问题来了：为什么p的指向n1可以不删？

答;原因是以及没人指向p了， 如果没人引用（指向）的东西，就会被系统自动回收。 像clear（）方法，head不指向首个节点，那么首个节点被回收，同理下面也如此。

五、Java自带的LinkedList 

 两个构造方法

方法解释
LinkedList()无参构造
public LinkedList(Collection c)使用其他集合容器中元素构造List
  1. public static void main(String[] args) {
  2. // 构造一个空的LinkedList
  3.     List<Integer> list1 = new LinkedList<>();
  4.     List<String> list2 = new java.util.ArrayList<>();
  5.     list2.add("JavaSE");
  6.     list2.add("JavaWeb");
  7.     list2.add("JavaEE");
  8. // 使用ArrayList构造LinkedList
  9.     List<String> list3 = new LinkedList<>(list2);
  10. }

 一些常用方法

方法解释
boolean add(E e)尾插 e
void add(int index, E element)将 e 插入到 index 位置
boolean addAll(Collection c)尾插 c 中的元素
E remove(int index)删除 index 位置元素
boolean remove(Object o)删除遇到的第一个 o
E get(int index)获取下标 index 位置元素
E set(int index, E element)将下标 index 位置元素设置为 element
void clear()清空
boolean contains(Object o)判断 o 是否在线性表中
int indexOf(Object o)返回第一个 o 所在下标
int lastIndexOf(Object o)返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)截取部分 list
  1. public static void main(String[] args) {
  2.     LinkedList<Integer> list = new LinkedList<>();
  3.     list.add(1); // add(elem): 表示尾插
  4.     list.add(2);
  5.     list.add(3);
  6.     list.add(4);
  7.     list.add(5);
  8.     list.add(6);
  9.     list.add(7);
  10.     System.out.println(list.size());
  11.     System.out.println(list);
  12. // 在起始位置插入0
  13.     list.add(0, 0); // add(index, elem): 在index位置插入元素elem
  14.     System.out.println(list);
  15.     list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
  16.     list.removeFirst(); // removeFirst(): 删除第一个元素
  17.     list.removeLast(); // removeLast(): 删除最后元素
  18.     list.remove(1); // remove(index): 删除index位置的元素
  19.     System.out.println(list);
  20. // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
  21. if(!list.contains(1)){
  22.     list.add(0, 1);
  23. }
  24.     list.add(1);
  25.     System.out.println(list);
  26.     System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
  27.     System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
  28.     int elem = list.get(0); // get(index): 获取指定位置元素
  29.     list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
  30.     System.out.println(list);
  31. // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
  32.     List<Integer> copy = list.subList(0, 3); 
  33.     System.out.println(list);
  34.     System.out.println(copy);
  35.     list.clear(); // 将list中元素清空
  36.     System.out.println(list.size());
  37. }

六、LinkedList的遍历

  1. public static void main(String[] args) {
  2.     LinkedList<Integer> list = new LinkedList<>();
  3.     list.add(1); // add(elem): 表示尾插
  4.     list.add(2);
  5.     list.add(3);
  6.     list.add(4);
  7.     list.add(5);
  8.     list.add(6);
  9.     list.add(7);
  10.     System.out.println(list.size());
  11. //for循环遍历
  12. for (int i = 0; i < list.size(); i++) {
  13.     System.out.print(list.get(i)+" ");
  14. }
  15. // foreach遍历
  16. for (int e:list) {
  17.     System.out.print(e + " ");
  18. }
  19.     System.out.println();
  20. // 使用迭代器遍历---正向遍历
  21.     ListIterator<Integer> it = list.listIterator();
  22. while(it.hasNext()){
  23.     System.out.print(it.next()+ " ");
  24. }
  25.     System.out.println();
  26. // 使用反向迭代器---反向遍历
  27.     ListIterator<Integer> rit = list.listIterator(list.size());
  28. while (rit.hasPrevious()){
  29.     System.out.print(rit.previous() +" ");
  30. }
  31.     System.out.println();
  32. }

七、ArrayList和LinkedList的区别  

不同点数组链表
存储方式连续内存空间分散内存空间
容量扩展长度不可变可灵活扩展
内存效率元素占用内存少、但可能浪费空间元素占用内存多
访问元素O(1)O(N)
添加元素O(N)O(1)
删除元素O(N)O(1)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/661683
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号