链表----在链表中添加元素详解--使用链表的虚拟头结点

在上一小节中关于在链表中头部添加元素与在其他位置添加元素在逻辑上有所差别，这是由于我们在给链表添加元素时需要找到待添加元素位置的前一个元素所在的位置，但对于链表头来说，没有前置节点，因此在逻辑上就特殊一些，操作方式也就有所差别，需单独处理。为了针对头结点的操作方式与其他方式一致：接下来我们就一步一步引入今天的主题--使用虚拟头结点。

首先来看看之前的节点结构--第一个是头结点

 相应的逻辑代码，感兴趣的可以看看我上一篇相关介绍，点击传送地址

 为了能把关于头结点的操作与其他操作统一起来，我们来分析一下情况：

问题：头结点没有前置节点，

解决办法：为头结点造一个前置节点（不存储任何东西）--虚拟头结点

此时链表结构为：

则dummyHead节点变为了0这个节点（头结点）的前置节点，则现在所有节点都有了前置节点，在逻辑可以使用统一的操作方式。下面对代码进行改写：

（1）将之前对头结点的定义改为对虚拟头结点的定义

将原来定义的头结点代码

private Node head;

改为

private Node dummyHead;

（2）链表构造函数初始化时对虚拟节点进行初始化

将原来对头结点的初始化

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

改为对虚拟节点的初始化，虚拟头节点为初始化为空节点。（空链表时存在一个唯一的虚拟头结点）

 //无参数构造函数
    public LinkedList() {
        dummyHead = new Node(null, null);
        size = 0;
    }

（3）改进之前的add（int index,E e）方法，之前对在头结点添加元素单独做了处理（if-else判断），如下：

 1  //在链表的index(0--based)的位置添加新的元素e    (实际不常用，练习用)
 2
 3     public void add(int index, E e) {
 4         if (index < 0 || index > size) {
 5             throw new IllegalArgumentException("位置不合法");
 6         }
 7
 8         //对于头节点的特殊处理
 9         if (index == 0) {
10             addFirst(e);
11         } else {
12             Node prev = head;
13             for (int i = 0; i < index - 1; i++) {//获取到需要添加元素位置的前一个元素
14                 prev = prev.next;
15             }
16
17 //            Node node = new Node(e);
18 //            node.next = prev.next;
19 //            prev.next = node;
20
21             prev.next=new Node(e,prev.next);
22
23             size++;
24         }
25
26     }

由于现在已经统一了添加的逻辑，我们可以去掉if-else判断，prev初始时指向虚拟头结点（dummyHead），由于增加了一个虚拟头结点（dummyHead）且是从该节点开始计算，此时我们为了找到index前面一个节点，只需遍历index次。

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

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

        Node prev = dummyHead;//初始时prev指向dummyHead
        for (int i = 0; i < index; i++) {//获取到需要添加元素位置的前一个元素  从dummyHead开始遍历
            prev = prev.next;
        }

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

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

        size++;

    }

（4）改进addFirst()方法，该方法依托于add(int index,E e)方法

    //在链表头添加新的元素e
    public void addFirst(E e) {
        add(0, 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 dummyHead;
36
37     //节点个数
38     private int size;
39
40
41     //无参数构造函数
42     public LinkedList() {
43         dummyHead = new Node(null, 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     //在链表的index(0--based)的位置添加新的元素e    (实际不常用，练习用)
58
59     public void add(int index, E e) {
60         if (index < 0 || index > size) {
61             throw new IllegalArgumentException("位置不合法");
62         }
63
64         Node prev = dummyHead;//初始时prev指向dummyHead
65         for (int i = 0; i < index; i++) {//获取到需要添加元素位置的前一个元素  从dummyHead开始遍历
66             prev = prev.next;
67         }
68
69 //            Node node = new Node(e);
70 //            node.next = prev.next;
71 //            prev.next = node;
72
73         prev.next = new Node(e, prev.next);
74
75         size++;
76
77     }
78
79     //在链表头添加新的元素e
80     public void addFirst(E e) {
81         add(0, e);
82     }
83
84     //在链表末尾添加新的元素
85     public void addLast(E e) {
86         add(size, e);
87     }
88 }

本小节着重介绍了虚拟头节点的使用，若您觉得本文还行、还过得去，麻烦给个推荐吧，谢谢！！