【Java】/* 双向链表 - 底层实现 */

【难点】：remove、removeAllKey

一、IList

package bagfive;/*** Created with IntelliJ IDEA.* Description:* User: tangyuxiu* Date: 2024-08-21* Time: 20:30*/
public interface IList<E> {//头插法void addFirst(E data);//尾插法void addLast(E data);//任意位置插入,第一个数据节点为0号下标void addIndex(int pos,E data);//查找是否包含关键字key是否在单链表当中boolean contains(E key);//删除第一次出现关键字为key的节点void remove(E key);//删除所有值为key的节点void removeAllKey(E key);//得到单链表的长度int size();void display();void clear();
}

二、MyLinkedList

package bagfive;/*** Created with IntelliJ IDEA.* Description:* User: tangyuxiu* Date: 2024-08-21* Time: 20:30*/
public class MyLinkedList<E> implements IList<E> {/* 使用内部类定义双向链表节点 */private static class ListNode<E> {E val;ListNode<E> prev;ListNode<E> next;public ListNode(E val) {this.val = val;}}private ListNode<E> head;private ListNode<E> last;@Overridepublic void addFirst(E data) {ListNode<E> newNode = new ListNode<>(data);//1. 如果链表为nullif (this.head == null) {this.head = this.last = newNode;return;}//2. 链表不为nullnewNode.next = this.head;this.head.prev = newNode;this.head = newNode;}@Overridepublic void addLast(E data) {ListNode<E> newNode = new ListNode<>(data);//1. 如果链表为nullif (this.head == null) {this.head = this.last = newNode;return;}//2. 链表不为nullthis.last.next = newNode;newNode.prev = this.last;this.last = newNode;}/* 判断add的位置是否合法 */private boolean addIndexIsLegal(int pos) {if (pos < 0 || pos > this.size()) {return false;}return true;}@Overridepublic void addIndex(int pos, E data) {//1. 判断pos位置是否合法if (!this.addIndexIsLegal(pos)) {return;}//2. pos == 0if (pos == 0) {this.addFirst(data);return;}//3. pos == size()if (pos == this.size()) {this.addLast(data);return;}//4. 其他位置,不需要找前驱节点了ListNode<E> newNode = new ListNode<>(data);ListNode<E> cur = this.head;for (int i = 0; i < pos; i++) {cur = cur.next;}newNode.next = cur;cur.prev.next = newNode;newNode.prev = cur.prev;cur.prev = newNode;}@Overridepublic boolean contains(E key) {ListNode<E> cur = this.head;while (cur != null) {if (cur.val.equals(key)) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(E key) {// 头，任意，尾 (链表为null进不去循环)ListNode<E> del = this.head;while (del != null) {if (del.val.equals(key)) {if (this.head == del) {//如果为头节点if (this.head.next == null) {//如果为头节点，且链表只有一个节点this.head = this.last = null;} else {this.head = this.head.next;this.head.prev = null;}} else {if (this.last == del) {//如果为尾节点this.last = this.last.prev;this.last.next = null;} else {//其他位置del.prev.next = del.next;del.next.prev = del.prev;}}return;}del = del.next;}}@Overridepublic void removeAllKey(E key) {// 头，只一个节点，任意，尾 (链表为null进不去循环)ListNode<E> del = this.head;while (del != null) {if (del.val.equals(key)) {if (this.head == del) {//如果为头节点if (this.head.next == null) {//如果为头节点，且链表只有一个节点this.head = this.last = null;} else {this.head = this.head.next;this.head.prev = null;}} else {if (this.last == del) {//如果为尾节点this.last = this.last.prev;this.last.next = null;} else {del.prev.next = del.next;//其他位置del.next.prev = del.prev;}}}del = del.next;}}@Overridepublic int size() {int count = 0;ListNode<E> cur = this.head;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void display() {ListNode<E> cur = this.head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}@Overridepublic void clear() {ListNode<E> cur = this.head;while (cur != null) {cur.val = null;cur = cur.next;}this.head = this.last = null;//🙀}
}