Java代碼展示數(shù)據(jù)結(jié)構(gòu)中鏈表的增刪改查

class ListNode {
    public int val;//數(shù)值
    public ListNode next;//下一個(gè)節(jié)點(diǎn)的地址

    public ListNode(int val) {
        this.val = val;
    }
}

//頭插法
public void addFirst(int data) {
    ListNode node = new ListNode(data);
    node.next = this.head;
    this.head = node;
}

//尾插法
public void addLast(int data) {
    ListNode node = new ListNode(data);
    ListNode cur = this.head;
    //第一次插入
    if(this.head == null) {
        this.head = node;
    }else{
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

//得到單鏈表的長(zhǎng)度
public int size() {
    int count = 0;
    ListNode cur = this.head;
    while (cur != null) {
        cur = cur.next;
        count++;
    }
    return count;
}

  /**
     * 讓 cur 向后走 index - 1 步
     * @param index
     * @return
     */
public ListNode findIndexSubOne(int index) {
    int count = 0;
    ListNode cur = this.head;
    while (count != index-1) {
        cur = cur.next;
        count++;
    }
    return  cur;
}
//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)
public void addIndex(int index,int data) {
    //判斷合法性
    if(index < 0 || index > size()) {
            System.out.println("index位置不合法");
            return;
    }
    //頭插法
    if(index == 0) {
        this.addFirst(data);
        return;
    }
    //尾插法
    if(index == size()) {
        this.addLast(data);
        return;
    }
    //找前驅(qū),cur指向的是 index 的前一個(gè)節(jié)點(diǎn)
    ListNode cur = findIndexSubOne(index);
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = node;
}

//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

/**
  * 找要?jiǎng)h除 key 的前一個(gè)節(jié)點(diǎn)
 * @return
 */
public ListNode searchPrev(int key) {
    ListNode prev = this.head;
    while (prev.next != null) {
        if (prev.next.val == key) {
            return prev;
        }
        prev = prev.next;
    }
    return null;
}
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
public void remove(int key) {
    if(this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    //找 key 的前驅(qū)節(jié)點(diǎn)
    ListNode prev = searchPrev(key);
    if(prev == null) {
        System.out.println("沒(méi)有key這個(gè)關(guān)鍵字");
        return;
    }
    //刪除
    ListNode delete = prev.next;
    prev.next = delete.next;
}

//刪除所有值為key的節(jié)點(diǎn)
public void removeAllKey(int key) {
    ListNode prev = this.head;
    ListNode cur = this.head.next;
    while (cur != null) {
        if(cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        }else {
            prev = cur;
            cur = cur.next;
        }
    }
    //判斷第一個(gè)節(jié)點(diǎn)是否是要?jiǎng)h除的節(jié)點(diǎn)
    if(this.head.val == key) {
        this.head = this.head.next;
    }
}

//打印鏈表
public void display() {
    ListNode cur = this.head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

//置空鏈表
public void clear() {
    ListNode cur = this.head;
    //一個(gè)個(gè)制空
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = null;
        cur = curNext;
    }
    this.head = null;
}

public class TestLinkedList {
    public ListNode head;
    public ListNode last;
}

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

    public ListNode (int val) {
        this.val = val;
    }
}

//頭插法
public void addFirst(int data) {
    ListNode node = new ListNode(data);
    //第一次插入
    if(this.head == null) {
        this.head = node;
        this.last = node;
    }else {
        head.prev = node;
        node.next = this.head;
        this.head = node;
    }
}

//尾插法
public void addLast(int data) {
    ListNode node = new ListNode(data);
    //第一次插入
    if(this.head == null) {
        this.head = node;
        this.last = node;
    }else {
        this.last.next = node;
        node.prev = this.last;
        this.last = node;
    }
}

//得到鏈表的長(zhǎng)度
public int size() {
    ListNode cur = this.head;
    int count = 0;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

//找要插入的節(jié)點(diǎn)的位置
public ListNode searchIndex(int index) {
    ListNode cur = this.head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    return  cur;
}
//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)
public void addIndex(int index,int data) {
    //判斷index位置的合法性
    if(index < 0 || index > this.size()) {
        System.out.println("index的位置不合法");
        return;
    }
    //頭插法
    if(index == 0) {
        this.addFirst(data);
        return;
    }
    //尾插法
    if(index == this.size()) {
        this.addLast(data);
        return;
    }
    //中間插入
    ListNode node = new ListNode(data);
    ListNode cur = searchIndex(index);
    node.next = cur;
    node.prev = cur.prev;
    cur.prev.next = node;
    cur.prev = node;
}

//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
public void remove(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            //要?jiǎng)h除的是頭節(jié)點(diǎn)
            if(this.head == cur) {
                this.head = this.head.next;
                this.head.prev = null;
            }else {
                //尾巴節(jié)點(diǎn)和中間的節(jié)點(diǎn)兩種情況
                cur.prev.next = cur.next;
                if(this.last == cur) {
                    //刪除尾巴節(jié)點(diǎn)
                    cur = cur.prev;
                }else {
                    cur.next.prev = cur.prev;
                }
            }
            //已經(jīng)刪完了
            return;
        }else {
            cur = cur.next;
        }
    }
}

//刪除所有值為key的節(jié)點(diǎn)
public void removeAllKey(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            //要?jiǎng)h除的是頭節(jié)點(diǎn)
            if(this.head == cur) {
                this.head = this.head.next;
                //假設(shè)全部是要?jiǎng)h除的節(jié)點(diǎn)
                if(this.head != null) {
                    this.head.prev = null;
                }else {
                 //防止最后一個(gè)節(jié)點(diǎn)不能被回收
                 this.last = null;
                }
            }else {
                //尾巴節(jié)點(diǎn)和中間的節(jié)點(diǎn)兩種情況
                cur.prev.next = cur.next;
                if(this.last == cur) {
                    //刪除尾巴節(jié)點(diǎn)
                    cur = cur.prev;
                }else {
                    cur.next.prev = cur.prev;
                }
            }
            //走一步
            cur = cur.next;
        }else {
            cur = cur.next;
        }
    }
}

//打印鏈表
public void display() {
    ListNode cur = this.head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

//置空鏈表
public void clear() {
    ListNode cur = this.head;
    //一個(gè)一個(gè)置空
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = curNext;
    }
    this.head = null;
    this.last = null;
}