devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

自己实现链表的基本操作方法（详细）（Java实现）_public boolean

作者：你好赵伟 | 2024-07-14 04:06:53

赞

踩

public boolean

目录

1.add( ) 方法：

（1）boolean add( Long e) ：链表尾插元素 e

（2）boolean add(int index, Long e):根据下标插入元素 e 

2. remove () 方法： 

（1）public Long remove (int index) 删除指定下标位置结点，返回被删除的结点元素值：

 （2）public boolean remove (Long e) 从前向后找，删除第一个遇到的 e 的结点：

3. public Long get ( int index) 获取指定下标元素值：

4. public Long set ( int index, Long e ) 将指定下标位置的元素值改为 e ，并返回原来的元素值：

5. public void clear () 清空链表中的所有结点：

6.  public int indexOf ( Long e) 从前向后，查找链表中指定元素的下标：

7. public int lastindexOf ( Long e) 从后向前，查找链表中指定元素的下标：

8. public boolean contains ( Long e) 判断链表中是否包含元素 e ：

9. public boolean isEmpty () 判断链表是否为空链表：

因为链表类也实现了线性表接口的方法，所以链表的基本操作方法和顺序表一样。这里我们定义链表中的元素类型为包装类（体现对象的形式而不是基本类型）

  这里提前定义了 MyNode 类，其中的属性为：Long val；MyNode prev；MyNode next；三个属性，一个元素值 val ，一个指向前一个结点的引用 prev，一个指向后一个结点的引用 next。

  1. public class MyNode {
  2.     public Long val;
  3.     MyNode prev;
  4.     MyNode next;
  5.  
  6.     public MyNode(Long val) {
  7.         this.val = val;
  8.         this.next = this.prev = null;
  9.     }
  10.  
  11. }

  在 MyLinkedList 类（自定义链表类）中实现自定义基本方法，其中包括属性 MyNode head；MyNode last；int size；三个属性，一个是引用 head 用于指向链表第一个结点，一个是引用 last 用于指向链表最后一个结点。

（代码放在最后了）

1.add( ) 方法：

（1）boolean add( Long e) ：链表尾插元素 e

 先分析尾插操作的主要步骤：

 ① 将链表的最后一个结点的 next 指向要插入的结点对象 node 。 

 ② 将要插入的结点的 prev 指向链表最后一个结点对象。

 ③ 将要插入的结点的 next 指向 null 。（也可以不写，因为初始化时候已经定义过了）

 ④ 更新链表的 last 引用，要让 last 始终指向链表中的最后一个结点。

 ⑤ 最后链表内结点数 size 加 1。

再考虑可能发生的情况： 

① 链表 size = 0 时，链表中没有结点：尾插后链表中只有被插入的结点，直接将链表的头结点引用和尾结点引用指向被插入结点即可，此时 node 结点的 prev 和 next 都指向 null。

② 链表 size > 0 时，使用主要步骤进行操作即可。

代码： 

  1. public boolean add(Long e) {
  2.         MyNode node = new MyNode(e);
  3.  
  4.         if (size == 0){
  5.             this.head = this.last = node;
  6.             node.prev = null; //可以不写，初始化已经置空过
  7.         }else{
  8.             this.last.next = node;
  9.             node.prev = this.last;
  10.             this.last = node;
  11.         }
  12.         size++;
  13.         return true;
  14.     }

（2）boolean add(int index, Long e):根据下标插入元素 e 

主要步骤：改变 4 个引用

① curNode 要移动到指定下标处。目标下标为 0 ，跳 0 下；目标下标为 2 ，跳 2 下；目标下标为 3 ，跳 3 下。总结规律可得，跳 index 下即可到目标下标处。（循环次数）

② 因为要将 e 插入指定下标处，所以需要指定下标处的上一个结点，所以提前记录 prevNode 指向指定下标的上一个结点。

③ 进行 prevNode 和 curNode 引用指向的改变。

④ 进行 node 引用指向的改变 。

考虑可能的情况：

头插：（和尾插思考方式一样）

代码：

  1. public void add(int index, Long e) {
  2.         MyNode node = new MyNode(e);
  3.         node.prev = null;
  4.         if (index < 0 || index > size){
  5.             throw new RuntimeException("下标不合法");
  6.         }
  7.         if (size == 0){
  8.             this.head = this.last = node;
  9.             node.next = null;
  10.             return;
  11.         }
  12.         if (size == 1){
  13.             if (index == 0){
  14.                 addaFirst(e);
  15.                 return;
  16.             }else {
  17.                 add(e);
  18.                 return;
  19.             }
  20.         }
  21.         //代码如果执行到这里，只剩下一种情况，就是 size > 1
  22.         //所以可以不使用 if 语句进行判断 size 的情况
  23.         if (index == 0){
  24.             addaFirst(e);
  25.             return;
  26.         }else if(index == size){
  27.             add(e);
  28.             return;
  29.         }
  30.         //代码执行到这里，说明以上的情况都不是。则此时的情况应使用改变 4 个引用的操作。
  31.         MyNode curNode = this.head;
  32.         for (int i = 0; i < index; i++) {
  33.             curNode = curNode.next;
  34.         }
  35.         MyNode prevNode = curNode.prev;
  36.         prevNode.next = node;
  37.         curNode.prev = node;
  38.         node.prev = prevNode;
  39.         node.next = curNode;
  40.  
  41.         size++;
  42.         return;
  43.     }

其中的 addFirst ()方法：头插

  1. //头插（为了代码的方便）
  2.     public boolean addaFirst(Long e){
  3.         MyNode node = new MyNode(e);
  4.         node.prev = null;
  5.         if (size == 0){
  6.             this.head = this.last = node;
  7.             node.next = null;
  8.         }else {
  9.             this.head.prev = node;
  10.             node.next = this.head;
  11.             this.head = node;
  12.         }
  13.         this.size++;
  14.         return true;
  15.     }

2. remove () 方法： 

（1）public Long remove (int index) 删除指定下标位置结点，返回被删除的结点元素值：

主要思路：

① 删除这个结点，需要让它的前一个结点越过它，指向它的后一个结点。所以需要定义三个引用

：curNode（指向指定位置结点）、prevNode（指向它的前一个结点）、nextNode（指向它的后一个结点）。

② 改变 2 个引用：让 prevNode 的 next 指向 nextNode ；让 nextNode 的 prev 指向 prevNode 。

③ size - 1。

④ 注意：因为要返回被删除的元素值，所以在改变引用前，需要提前把原来的元素值存起来。 

头删和尾删：

 

※考虑可能出现的情况： 

 

代码： 

  1. //删除指定下标位置的结点，返回被删除的元素值
  2.     @Override
  3.     public Long remove(int index) {
  4.         if (index < 0 ||index >= size){
  5.             //包括 size = 0 的情况
  6.             throw new RuntimeException("当前下标不合法");
  7.         }
  8.         if (size == 1){
  9.             Long e = this.head.val;
  10.             this.head = this.last = null;
  11.             size = 0;
  12.             return e;
  13.         }
  14.  
  15.         if (index == 0){
  16.             //头删
  17.             Long e = this.head.val;
  18.             this.head = this.head.next;
  19.             this.head.prev = null;
  20.             size--;
  21.             return e;
  22.         }
  23.         if (index == size - 1){
  24.             Long e = this.last.val;
  25.             this.last = this.last.prev;
  26.             this.last.next = null;
  27.             size--;
  28.             return e;
  29.         }
  30.         //代码执行到这里，说明以上情况都不是，此时：
  31.         // size > 1 && index > 0 && index < size - 1
  32.         MyNode curNode = this.head;
  33.         for (int i = 0; i < index; i++) {
  34.             curNode = curNode.next;
  35.         }
  36.         MyNode prevNode = curNode.prev;
  37.         MyNode nextNode = curNode.next;
  38.         Long e = curNode.val;
  39.  
  40.         prevNode.next = nextNode;
  41.         nextNode.prev = prevNode;
  42.  
  43.         size--;
  44.         return e;
  45.     }

 （2）public boolean remove (Long e) 从前向后找，删除第一个遇到的 e 的结点：

主要思路：跟上面的大同小异，主要是可能的情况不同。

① 注意：在元素结点个数 size = 1 时，进行主要思路的改变 2 个引用的操作时，要特别注意 尾结点 last 的改变。

可能出现的情况：

 代码：

  1. //从前向后找，删除第一个遇到的 e
  2.     @Override
  3.     public boolean remove(Long e) {
  4.         MyNode curNode = this.head;
  5.         //将有元素 e 的情况都放在循环里，如果循环结束后，还没有返回，则说明该链表中没有元素 e ，删除失败，返回 false
  6.         for (int i = 0; i < size; i++) {
  7.             if (curNode.val.equals(e)) {
  8.                 if (i == 0){
  9.                     //进行头删
  10.                     this.head = this.head.next;
  11.                     //此时 size 可能 = 1，也可能 > 1
  12.                     //本来头删的下一步为： this.head.prev = null ;
  13.                     //但是如果 size = 1 的话，this.head = this.head.next 后，this.head = null
  14.                     //如果执行这句话，就会发生空指针异常的错误。所以我们还要分一次情况分别讨论
  15.                     if (this.head != null){
  16.                         this.head.prev = null;
  17.                         size--;
  18.                         return true;
  19.                     }else {
  20.                         // size = 1  链表中只有一个元素的情况，执行完 this.head = this.head.next 后为空链表
  21.                         this.last = null;
  22.                         size--;
  23.                         return true;
  24.                     }
  25.                 }
  26.  
  27.                 if (i == size - 1){
  28.                     //进行尾删
  29.                     this.last = this.last.prev;
  30.                     //这里也要思考，有没有上面的情况出现
  31.                     //不会出现上面的情况，因为如果 size = 1 的话，e 只能出现在 i = 0 的时候。即 e 的下标为 0，进行头删操作
  32.                     //所以如果代码走到这里，size 至少为 2 并且 i = 1，即尾删操作
  33.                     this.last.next = null;
  34.                     size--;
  35.                     return true;
  36.                 }
  37.  
  38.                 //代码走到这里，只剩下一种情况，要删的元素在中间结点。
  39.                 //中间结点的特点是，既有前驱元素，也有后继元素，所以不用担心会出现空指针异常的错误出现
  40.                 MyNode prevNode = curNode.prev;
  41.                 MyNode nextNode = curNode.next;
  42.  
  43.                 prevNode.next = nextNode;
  44.                 nextNode.prev = prevNode;
  45.                 size--;
  46.                 return true;
  47.             }
  48.             curNode = curNode.next;
  49.         }
  50.         return false;
  51.     }

3. public Long get ( int index) 获取指定下标元素值：

主要思路：

① 涉及到下标传参，首先要考虑下标不合法的情况。

② 要将 curNode 结点移动到指定下标结点下，需要进行循环。循环后返回结点的 val 即可。

代码：

  1.  //获取指定下标的元素值
  2.     @Override
  3.     public Long get(int index) {
  4.         if (index < 0 || index >= size){
  5.             throw new RuntimeException("下标不合法");
  6.         }
  7.         MyNode curNode = this.head;
  8.         for (int i = 0; i < index; i++) {
  9.             curNode = curNode.next;
  10.         }
  11.         return curNode.val;
  12.     }

4. public Long set ( int index, Long e ) 将指定下标位置的元素值改为 e ，并返回原来的元素值：

主要思路：

① 考虑下标不合法的情况。

② 将引用 curNode 移动到指定下标结点处。

③ 将原来的 val 值提前记录，再改变结点对象的 val 值。

代码：

  1. //将指定下标位置元素值换成 e ，并返回被修改的元素值
  2.     @Override
  3.     public Long set(int index, Long e) {
  4.         if (index < 0 || index >= size){
  5.             throw new RuntimeException("下标不合法");
  6.         }
  7.         MyNode curNode = this.head;
  8.         for (int i = 0; i < index; i++) {
  9.             curNode = curNode.next;
  10.         }
  11.         Long a = curNode.val;
  12.         curNode.val = e;
  13.         return a;
  14.     }

5. public void clear () 清空链表中的所有结点：

主要思路：

将链表的头结点和尾结点都置空，同时结点个数 size 置零。

代码：

  1.  @Override
  2.     public void clear() {
  3.         this.head = this.last = null;
  4.         size = 0;
  5.     }

6.  public int indexOf ( Long e) 从前向后，查找链表中指定元素的下标：

主要思路： 

① 因为链表和链表结点中，没有存储下标的属性，所以需要我们自己定义一个变量 i 来表示下标。

② 进行循环判断。

③ 每次在将 curNode 指向下一个结点的同时，i 要进行加 1 的操作。（ i 从 0 开始）

④ 如果找不到的话，返回 -1 。

代码：

  1.  @Override
  2.     public int indexOf(Long e) {
  3.         MyNode curNode = this.head;
  4.         int i = 0; //表示 curNode 此时的下标
  5.         while (curNode != null){
  6.             if (curNode.val.equals(e)){
  7.                 return i;
  8.             }
  9.             i++;
  10.             curNode = curNode.next;
  11.         }
  12.         return -1;
  13.     }

7. public int lastindexOf ( Long e) 从后向前，查找链表中指定元素的下标：

主要思路：跟从前向后查找一样，唯一区别是：这里的 i 应该从 size - 1 开始，依次递减。

代码：

  1.  @Override
  2.     public int lastindexOf(Long e) {
  3.         MyNode curNode = this.last;
  4.         int i = size - 1; // 表示 curNode 此时的下标
  5.         while (curNode != null){
  6.             if (curNode.val.equals(e)){
  7.                 return i;
  8.             }
  9.             i--;
  10.             curNode = curNode.prev;
  11.         }
  12.         return -1;
  13.     }

8. public boolean contains ( Long e) 判断链表中是否包含元素 e ：

主要思路：只要链表中有元素 e 就返回 true ，所以我们可以直接调用 indexOf () 方法进行判断。

代码：

  1.  @Override
  2.     public boolean contains(Long e) {
  3.         return indexOf(e) != -1;
  4.  
  5.     }

9. public boolean isEmpty () 判断链表是否为空链表：

主要思路： 空链表代表链表结点个数为 0 。

代码：

  1. @Override
  2.     public boolean isEmpty() {
  3.         return size == 0;
  4.     }

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

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

  

闽ICP备14008679号