【Java】/* 单向链表 - 底层实现 */
【难点】：remove、removeAllKey
一、IList
package bagfour;/*** Created with IntelliJ IDEA.* Description:* User: tangyuxiu* Date: 2024-08-20* Time: 20:58*/
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 clear();void display();
}
二、MyLinkedList
package bagfour;/*** Created with IntelliJ IDEA.* Description:* User: tangyuxiu* Date: 2024-08-20* Time: 20:58*/
public class MyLinkedList<E> implements IList<E> {/* 使用内部类来定义链表节点 */private static class ListNode<E> {E val;ListNode<E> next;//默认为nullpublic ListNode(E val) {this.val = val;}}private ListNode<E> head;/* 头插 */@Overridepublic void addFirst(E data) {ListNode<E> newNode = new ListNode<>(data);this.head.next = this.head;this.head = newNode;}/* 尾插 */@Overridepublic void addLast(E data) {ListNode<E> newNode = new ListNode<>(data);//1. 如果链表为nullif (this.head == null) {this.head = newNode;return;}//2. 尾插ListNode<E> cur = this.head;while (cur.next != null) {cur = cur.next;}cur.next = newNode;}/* 判断add位置是否合法 */private boolean addIndexIsLegal(int pos) {if (pos < 0 || pos > this.size()) {return false;}return true;//如果链表为null,且pos位置为0,此时也是合法的}/* 任意位置插入 */@Overridepublic void addIndex(int pos, E data) {//1. 判断add位置是否合法if (!this.addIndexIsLegal(pos)) {return;}//2. pos == 0（链表为null且index=0,也走的这里）if (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;//寻找pos节点的前一个节点//【思路】本来想要找到到index下标所指向的节点的，但发现// 我们要找的其实不是index下标所指向的节点而是要找到它的前一个节点// 那么我们将cur原本要走的index步，改为走index - 1步即可for (int i = 0; i < pos - 1; i++) {//这里的问题头插部分已经考虑到了🙀cur = cur.next;}newNode.next = cur.next;cur.next = 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;}/* 删除第一次出现关键字为key的节点 */@Overridepublic void remove(E key) {//1. 如果链表为nullif (this.head == null) {return;}//2. 如果key在头节点处if (this.head.val.equals(key)) {this.head = this.head.next;return;}//3. 如果key在其他位置ListNode<E> pre = this.head;//找到key的前一个节点while (pre.next != null) {ListNode<E> del = pre.next;if (del.val.equals(key)) {pre.next = del.next;return;}pre = pre.next;}}/* 删除所有值为key的节点 */@Overridepublic void removeAllKey(E key) {//1. 如果链表为nullif (this.head == null) {return;}//2. 其他位置ListNode<E> pre = this.head;ListNode<E> del = pre.next;while (pre.next != null) {if (del.val.equals(key)) {pre.next = del.next;//del = del.next;} else {pre = pre.next;//del = del.next;}del = del.next;}//3. 如果key在头节点处if (this.head.val.equals(key)) {//为什么下行代码不写成pre = pre.next呢？//答：“正常”的代码中pre,find只是工具，真正的head一直仍然指向的是同一个节点this.head = this.head.next;}}/* 得到单链表的长度 */@Overridepublic int size() {int count = 0;ListNode<E> cur = this.head;while (cur != null) {count++;cur = cur.next;}return count;}/* 清空链表 */@Overridepublic void clear() {ListNode<E> cur = this.head;while (cur != null) {cur.val = null;cur = cur.next;}this.head = null;}/* 打印 */@Overridepublic void display() {ListNode<E> cur = this.head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}
}