对顺序表以及双向链表的理解

1
public interface IList {
2
    // 新增元素,默认在数组最后新增
3
    public void add(int data);
4
    // 在 pos 位置新增元素
5
    public void add(int pos, int data);
6
    // 判断数组是否已满
7
    public boolean isFull();
8
    // 判定是否包含某个元素
9
    public boolean contains(int toFind);
10
    // 查找某个元素对应的位置
11
    public int indexOf(int toFind);
12
    // 获取 pos 位置的元素
13
    public int get(int pos);
14
    // 给 pos 位置的元素设为 value
15
    public void set(int pos, int value);
16
    //删除第一次出现的关键字key
17
    public void remove(int toRemove);
18
    // 获取顺序表长度
19
    public int size() ;
20
    // 清空顺序表
21
    public void clear();
22
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
23
    public void display() ;
24
}

1
    @Override
2
    public void remove(int key) {
3
        if(this.head == null){
4
            return;
5
        }
6
        if(this.head.val == key){
7
            this.head = this.head.next;
8
            return;
9
        }
10
        // 创建当前节点cur
11
        ListNode cur = FindNodeBeforeKey(key);
12
        cur.next = cur.next.next;
13
    }
14

15
    // 查找到删除节点前的一个节点
16
    private ListNode FindNodeBeforeKey(int key){
17
        // 创建当前节点
18
        ListNode cur = this.head;
19
        // cur要每一个都走一遍
20
        while(cur.next != null){
21
            if(cur.next.val == key){
22
                return cur;
23
            }
24
            cur = cur.next;
25
        }
26
        return null;
27
    }

1
@Override
2
public void remove(int key) {
3
    ListNode cur = head;
4
    while(cur != null){
5
        if(cur.val == key){
6
            //删除在开头
7
            if(cur == head){
8
                head = head.next;
9
                if (head != null) {
10
                    // 情况 A: 至少还有两个节点，现在的 head 指向原第二个节点
11
                    head.prev = null;
12
                } else {
13
                    // 情况 B: 原本只有一个节点，删完后 head 为 null
14
                    // 必须同步清理 last
15
                    last = null;
16
                }
17
            } else{
18
                //删除在其他（中间、结尾）
19
                cur.prev.next = cur.next;
20
                if(cur.next == null){
21
                    last = last.prev;  // 该情况为删除在结尾
22
                } else{
23
                    cur.next.prev = cur.prev;
24
                }
25
            }
26
             return;
27
        }
28
        cur = cur.next;
29
    }
30
}