算法通关村第一关|青铜|链表笔记

1.理解 Java 如何构造出链表

在 Java 中，我们创建一个链表类，类中应当有两个属性，一个是结点的值 val ，一个是该结点指向的下一个结点 next 。 next 通俗讲是一个链表中的指针，但是在链表类中是一个链表类型的引用变量，这点是之前我会忽视的。所以根据面向对象的理论，在 Java 里规范的链表应该定义为：

public class ListNode {
    private int data;
    private ListNode next;
    public ListNode(int data){
        this.data = data;
    }
    public int getData(){
        return data;
    }
    public void setData(int data){
        this.data = data;
    }
    public ListNode getNext(){
        return next;
    }
    public void setNext(ListNode next){
        this.next = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

但是在算法题中为了精简会使用其他方式创建链表：

public class ListNode{
    // 使用了公共权限，可以直接访问到val和next的值
    public int val;
    public ListNode next;

    ListNode(int x){
        val = x;
        next = null;
    }
}
ListNode listnode = new ListNode(1);
1
2
3
4
5
6
7
8
9
10
11

2.链表增加元素时会有什么问题，该如何处理

当链表为空即 head 为 null 的时候，要插入的结点就是链表的头结点。当然也可以抛出不能插入的异常。

3.双向链表如何构造

双向链表就是每一个链表对象内部多存储一个前趋指针，写一个算法题中的精简版本：

public class DoublyListNode{
    public int val;
    public DoublyListNode prev;
    public DoublyListNode next;

    DoublyListNode(int x){
        val = x;
        prev = null;
        next = null;
    }
}
DoublyListNode doublyListnode = new DoublyListNode(1);
1
2
3
4
5
6
7
8
9
10
11
12

4.双向链表如何实现元素的插入和删除

双向链表与单向链表的不同之处就是双向链表的插入和删除都需要修改前趋和后继指针。

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤