3.2链表----在链表中添加元素详解

时间：2024-01-24 08:22:01

1.链表中头节点的引入

1.1基本的链表结构：

1.2对于链表来说，若想访问链表中每个节点则需要把链表的头存起来，假如链表的头节点为head，指向链表中第一个节点，如图：

1.3使用代码表示此时的链表

//定义头节点
    private Node head;

    //节点个数
    private int size;


    //无参数构造函数
    public LinkedList() {
        head = null;
        size = 0;
    }

    //获取链表中的元素个数
    public int getSize() {
        return size;
    }

    //返回链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

 2.在链表头添加元素

2.1初始时，假设链表如下：

2.2 如在链表头添加一个666元素则需要先将666放进一个节点里，在节点里存入这个元素以及相应的next。

操作如下：

第一步：现将666这个节点（node）的next指向head,代码如下：

node.next=head

图示为：

 

第二步：然后再将head指向新的节点666

head=node

图示为：

通过第一步、第二步，我们就成功将新节点添加到头节上。此时node这个变量也就结束了此轮的工作，结果变为：

2.3 在链表头添加新元素的相关代码

 //在链表头添加新的元素e
    public void addFirst(E e) {
        Node node = new Node(e);
        node.next = head;
        head = node;


        size++;
    }

等同于：

  //在链表头添加新的元素e
    public void addFirst(E e) {
        head = new Node(e, head);
        size++;
    }

2.4 在链表中间添加元素

假设初始链表为：

假设我们需要在索引为2的位置添加元素666（此时的索引为2只是用来说明我们此时需要操作的位置，并不是真正的索引意思）

操作步骤：

1）：创建出666这个节点

2）：使用一个变量prev来标识在需要插入节点的地方的前一个节点，初始时prev和头节点head是相同的。

 

对于此处我们需要在索引为2的位置插入新元素，我们只需要找到索引为2的前一个位置（索引为1），然后把prev指向索引为1节点即可。

 

3）：进行元素添加操作

第一步：先将node的next指向prev的下一个节点元素

node.next=prev.next

 

 

第二步：再将prev的next指向node

prev.next=node

通过第一步、第二步即可将新元素插入到索引为2的地方。

 从上不难看出，对于在链表中添加元素关键是找到要添加的节点的前一个节点，因此对于在索引为0的节点添加元素就需要单独处理。

关于在链表中间添加元素的代码：

 //在链表的index(0--based)的位置添加新的元素e    (实际不常用，练习用)

    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("位置不合法");
        }

        //对于头节点的特殊处理
        if (index == 0) {
            addFirst(e);
        } else {
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {//获取到需要添加元素位置的前一个元素
                prev = prev.next;
            }

            Node node = new Node(e);
            node.next = prev.next;
            prev.next = node;

            size++;
        }

    }

此时代码等同于：

  //在链表的index(0--based)的位置添加新的元素e    (时间不常用，练习用)

    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("位置不合法");
        }

        //对于头节点的特殊处理
        if (index == 0) {
            addFirst(e);
        } else {
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {//获取到需要添加元素位置的前一个元素
                prev = prev.next;
            }

//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;

            prev.next=new Node(e,prev.next);

            size++;
        }

    }

3.在链表尾部添加元素

这里复用上述的add（）方法

 //在链表末尾添加新的元素
    public void addLast(E e){
        add(size,e);
    }

 

本小节完整代码：

 1 package LinkedList;
 2 
 3 public class LinkedList<E> {
 4     //将Node节点设计成私有的类中类
 5     private class Node<E> {
 6         public E e;
 7         public Node next;
 8 
 9 
10         //两个参数的构造函数
11 
12         public Node(E e, Node next) {
13             this.e = e;
14             this.next = next;
15         }
16 
17         //一个参数的构造函数
18         public Node(E e) {
19             this.e = e;
20             this.next = null;
21         }
22 
23         //无参构造函数
24         public Node() {
25             this(null, null);
26         }
27 
28         @Override
29         public String toString() {
30             return e.toString();
31         }
32     }
33 
34     //定义头节点
35     private Node head;
36 
37     //节点个数
38     private int size;
39 
40 
41     //无参数构造函数
42     public LinkedList() {
43         head = null;
44         size = 0;
45     }
46 
47     //获取链表中的元素个数
48     public int getSize() {
49         return size;
50     }
51 
52     //返回链表是否为空
53     public boolean isEmpty() {
54         return size == 0;
55     }
56 
57 
58     //在链表头添加新的元素e
59     public void addFirst(E e) {
60         head = new Node(e, head);
61         size++;
62     }
63 
64     //在链表的index(0--based)的位置添加新的元素e    (实际不常用，练习用)
65 
66     public void add(int index, E e) {
67         if (index < 0 || index > size) {
68             throw new IllegalArgumentException("位置不合法");
69         }
70 
71         //对于头节点的特殊处理
72         if (index == 0) {
73             addFirst(e);
74         } else {
75             Node prev = head;
76             for (int i = 0; i < index - 1; i++) {//获取到需要添加元素位置的前一个元素
77                 prev = prev.next;
78             }
79 
80 //            Node node = new Node(e);
81 //            node.next = prev.next;
82 //            prev.next = node;
83 
84             prev.next=new Node(e,prev.next);
85 
86             size++;
87         }
88 
89     }
90 
91     //在链表末尾添加新的元素
92     public void addLast(E e){
93         add(size,e);
94     }
95 }

 关于本文，若您觉得本文还行、还过得去，麻烦给个推荐吧，谢谢！！

相关文章