LinkedList 链表

链表由一个个节点组成，节点内包含两部分，一部分是当前节点所存储的信息，另一部分是指向下一个节点的指针。链表也是栈和队列的底层实现方式之一。

什么是链表？

链表由一个个节点组成，节点内包含两部分，一部分是当前节点所存储的信息，另一部分是指向下一个节点的指针。它具有以下几个重要特性:

  1. 链表可以动态地增加数据，而不需要提前知道数据量地多少

  2. 链表允许插入和移除表上任意位置上的节点

  3. 链表不支持通过索引访问每一个节点，只能从头节点开始依次向后寻找，增加，删除，查找，修改均是如此。

通常链表可以用下面的图来表示：

除了虚拟头节点以外，其他所有节点都含有两部分，一部分是节点值，另一部分是指向下一个节点的指针，最后一个节点指向NULL。

因为链表中不同的节点并不是在内存中连续分配的，所以增，删，改，查，所有操作都只能通过虚拟头节点依次向后遍历节点。

什么是虚拟头节点，为什么需要它？

虚拟头节点本质上也是一个节点，只不过将它的值部分设为了NULL。

虚拟头节点存在的意义，主要有两个:

  1. 作为链表的入口，依次向后访问节点

  2. 用虚拟头节点，可以减少有些操作的复杂性(后面介绍)

构造一个链表

通过上面的介绍，我们很轻易地写出链表的构造函数

public class LinkedList<E> {

    private  class  Node{
        public E e;
        public Node next;

        public Node(E e, Node next){
            this.e=e;
            this.next=next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node dummyHead;
    int size;

    public LinkedList(){
        dummyHead=new Node(null,null);
        size=0;
    }
    
}

链表类内部有一个节点类 Node, 每一个节点有两个私有成员变量, val 和 next, 分别表示节点值 和 指向下一个节点的指针

链表构造函数会创建一个 dummyHead, val 和 next 都为 NULL， size 表示链表存储数据的个数，也就是非虚拟头节点的节点个数，初始值为0

链表一些有用的方法

获取 链表元素个数 和 判断 链表是否为空

public int getSize(){
    return  size;
}

public  boolean isEmpty(){
    return  size==0;
}

根据索引获取获得链表元素，这里的索引并不是真正意义上的索引，而是从第一个非虚拟头节点开始向后数第几个节点。我们用一个 cur 节点依次向后遍历。

public E get(int index){
    //索引越界,抛出异常
    if (index<0 || index>=size){
        throw new IllegalArgumentException("Get failed. Illegal index.");
    }
    Node cur=dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur=cur.next;
    }
    return cur.e;

}

获取链表第一个元素

public E getFirst(){
    return  get(0);
}

类似的还有 contains(E e) 查询某一元素是否存在, set(int index, E e)设置某一节点元素 都是类似的操作, 利用一个cur 节点依次向后遍历即可。

public  boolean contains(E e){
        Node cur=dummyHead.next;
        while (cur!=null){
            if (cur.e==e){
                return true;
            }
            cur=cur.next;
        }
        return  false;
}

public  void set(int index, E e){
    //索引越界抛出异常
    if (index<0 || index>=size){
        throw new IllegalArgumentException("Set failed. Illegal index.");
    }
    Node cur=dummyHead.next;
    for (int i = 0; i < index ; i++) {
        cur=cur.next;
    }
    cur.e=e;
}

向指定位置增加一个节点

add(int index,E e)用图表示这个过程如下

我们需要用到一个prev 指针，指向带加入位置的前一个节点，随后 new 一个新节点 newNode，newNode.next 指向pre.next，最后将prev.next 指向 新节点 即可。我们使用虚拟头节点，即使在第一个位置插入新节点，整个过程也是一样的，无需特殊处理。整个过程用代码表示如下:

public void add(int index,E e){
    //索引越界抛出异常
    if (index<0 || index>size){
        throw new IllegalArgumentException("Add failed. Illegal index.");
    }

    Node prev=dummyHead;
    for (int i = 0; i < index; i++) {
        prev=prev.next;
    }

    Node newNode= new Node(e);
    newNode.next=prev.next;
    prev.next=newNode;
    size++;

}

向链表头插入一个节点 addFirst(int index,E e)，向链表尾增加一个新节点addLast(int index,E e)都仅需调用add(int index,E e)

public  void addFirst(E e){
    add(0,e);
}

public void addLast(E e){
    add(size,e);
}

删除指定位置的节点并返回

remove(int index)用图表示这个过程如下

我们需要用到一个 prev 指针, 指向待删除的前一个节点。prev 指针初始化指向虚拟头节点 dummyHeadt。随后 prev 依次向后移动，当 prev 找到待删除节点前一个节点时， prev.next 指向的节点就是待删除的节点 delNode。将 prev.next 指向 delNode.next ，备份delNode成ret, 最后将 delNode 指向NULL ,返回 ret即可。整个过程用代码表示如下:

public E remove(int index){
    if(index<0 || index >=size){
        throw  new IllegalArgumentException("Delete failed, index shoud be >=0 and < size");
    }
    Node prev= dummyHead;
    for (int i = 0; i < index; i++) {
        prev=prev.next;
    }
    Node delNode=prev.next;
    prev.next=delNode.next;
    E ret=delNode.e;
    delNode=null;
    size--;
    return  ret;
}

删除含有某一个值的节点 removeElement(E e) 也与此类似

public void removeElement(E e){

    Node prev= dummyHead;
    Node cur=dummyHead.next;
    Node delNode=null;
    
    for (int i = 0; i < size ; i++) {
        if (cur.e==e){
            delNode=cur;
            prev.next=delNode.next;
            cur=null;
            break;
        }else {
            cur=cur.next;
            prev=prev.next;
        }
    }

    //若不存在, 抛出异常
    if (delNode==null){
        throw  new IllegalArgumentException("Doesn't contain e !!!");
    }

}

删除链表头节点 removeFirst() 和 删除链表尾节点 removeLast() 直接调用 remove(int index) 方法即可

public  E removeFirst(){
    return remove(0);
}

public  E removeLast(){
    return remove(size-1);
}

重写toString() 方法方便打印输出:

@Override
public String toString() {
    StringBuilder res= new StringBuilder();
    Node cur=dummyHead.next;
    while (cur!=null){
        res.append(cur+"->");
        cur=cur.next;
    }
    res.append("Null");
    return  res.toString();
}

测试一下

public class LinkedListTest {

    public static void main(String[] args) {
        LinkedList<Integer> linkedList =new LinkedList<>();

        for (int i = 0; i <5; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }
        
        linkedList.add(2,666);
        System.out.println(linkedList);

        linkedList.remove(2);
        System.out.println(linkedList);


        linkedList.removeElement(0);
        System.out.println(linkedList);

        linkedList.removeElement(888);//抛出异常,因为不存在这个元素
        System.out.println(linkedList);
    }
}

输出结果:

0->Null
1->0->Null
2->1->0->Null
3->2->1->0->Null
4->3->2->1->0->Null
4->3->666->2->1->0->Null
4->3->2->1->0->Null
4->3->2->1->Null
Exception in thread "main" java.lang.NullPointerException
	at LinkedList.removeElement(LinkedList.java:137)
	at LinkedListTest.main(LinkedListTest.java:20)
PreviousArray 动态数组NextStack 栈

Last updated

Was this helpful?