MyLinkedList类

java">public class MyLinkedList {// 定义节点类static class Node {int val;Node prev;Node next;public Node() {}public Node(int val) {this.val = val;}}// 定义头节点private Node head;// 定义尾结点private Node tail;// 头插public void headInsert(int val) {// 申请节点Node node = new Node(val);// 判空if (head == null) {// head 和 tail 都指向 nodehead = node;tail = node;return;}// head 不为空，则进行头插node.next = head;head.prev = node;// 重置头节点head = node;}// 尾插public void tailInsert(int val) {// 申请节点Node node = new Node(val);// 判空if (head == null) {head = node;tail = node;return;}// 非空情况下进行尾插tail.next = node;node.prev = tail;// 重置尾结点tail = node;}// 在 index 处插入元素public void randomInsert(int index, int val) {// 判空if (head == null) return;// 下标判断if (index < 0 || index > size()) {throw new IndexOfLinkedListException("下标 index :" + index + " 出现异常！");}// 头插if (index == 1) {headInsert(val);return;}// 尾插if (index == size()) {tailInsert(val);return;}// 找到要插入的位置Node cur = head;Node node = new Node(val);for (int i = 0; i < index; i++) {cur = cur.next;}// 进行插入cur.prev.next = node;node.next = cur;node.prev = cur.prev;cur.prev = node;}// 删除与 val 相等的元素节点public void remove(int val) {// 判空if (head == null) return;Node cur = head;while (cur != null) {// 值相等，进行删除if (cur.val == val) {// 头节点的情况if (cur == head) {head = head.next;head.prev = null;break;}// 尾结点的情况if (cur == tail) {tail = tail.prev;tail.next = null;break;}// 中间节点删除cur.prev.next = cur.next;cur.next.prev = cur.prev;}cur = cur.next;}}// 删除 index 处的元素public void removeOfIndex(int index) {// 判空if (head == null) return;// 下标判断if (index < 0 || index > size()) {throw new IndexOfLinkedListException("下标 index :" + index + " 出现异常！");}// 头删if (index == 1) {head = head.next;head.prev = null;return;}// 尾删if (index == size()) {tail = tail.prev;tail.next = null;return;}// 找到要删除的位置Node cur = head;for (int i = 1; i < index; i++) {cur = cur.next;}// 进行删除操作cur.prev.next = cur.next;cur.next.prev = cur.prev;}// 删除所有与 val 相等的节点public void removeAllVal(int val) {// 判空if (head == null) return;// 判断 val 值是否在链表中出现if (!contains(val)) return;// 从头节点开发判断Node cur = head;while (cur != null) {// 相等则进行删除if (cur.val == val) {// 是头节点的情况if (head == cur) {// head 走到下一个节点处head = head.next;head.prev = null;} else if (tail == cur) {// tail 走到上一个节点处tail = tail.prev;tail.next = null;} else {// 中间节点，让删除节点的前一个节点和后一个节点进行连接cur.next.prev = cur.prev;cur.prev.next = cur.next;}}// 注意，cur 无论是否删除了当前节点，都应该要走到下一步cur = cur.next;}}// 查找 val 第一次出现的下标public int indexOf(int val) {// 判空if (head == null) return -1;Node cur = head;for (int i = 1; i < size() + 1; i++) {// 找到了if (cur.val == val) {return i;}cur = cur.next;}// 没找到return -1;}// 查找 val 最后一次出现的下标public int lastOfIndex(int val) {// 判空if (head == null) return -1;int index = -1;Node cur = tail;for (int i = size(); i > 0; i--) {// 找到了if (cur.val == val) {index = i;}cur = cur.prev;}// 没找到return index;}// 判断 val 是否在链表中public boolean contains(int val) {// 判空if (head == null) return false;Node cur = head;while (cur != null) {// 找到了if (cur.val == val) {return true;}cur = cur.next;}// 没找到return false;}// 获取元素个数public int size() {Node cur = head;// 获取链表中的元素个数int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}// 打印链表public void display() {Node cur = head;// 进行打印操作while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}// 换行System.out.println();}// 清空链表public void clear() {Node cur = head;// 把每个节点都置为 nullwhile (cur != null) {Node tmp = cur.next;cur.next = null;cur.prev = null;cur = tmp;}// 头节点和尾结点置空head = null;tail = null;}
}

 

IndexOfLinkedListException类

java">public class IndexOfLinkedListException extends RuntimeException {public IndexOfLinkedListException() {}public IndexOfLinkedListException(String message) {super(message);}
}

 

 Test类

java">public class Test {public static void main(String[] args) {MyLinkedList linkedList = new MyLinkedList();// 头插linkedList.headInsert(1);linkedList.headInsert(2);linkedList.headInsert(3);// 打印链表linkedList.display();// 获取长度System.out.println(linkedList.size());// 尾插linkedList.tailInsert(4);linkedList.tailInsert(5);linkedList.tailInsert(6);linkedList.display();System.out.println(linkedList.size());// 任意位置插入linkedList.randomInsert(1, 7);linkedList.randomInsert(1, 7);linkedList.randomInsert(1, 7);linkedList.randomInsert(8, 8);linkedList.display();linkedList.randomInsert(8, 7);linkedList.display();linkedList.randomInsert(8, 8);linkedList.display();System.out.println(linkedList.size());linkedList.randomInsert(2, 111);linkedList.randomInsert(3, 111);linkedList.display();System.out.println(linkedList.size());// 删除所有和 val 相等的节点linkedList.removeAllVal(7);linkedList.display();System.out.println(linkedList.size());// 删除链表中第一个 val 相等的节点linkedList.remove(111);linkedList.remove(6);linkedList.remove(3);linkedList.display();System.out.println(linkedList.size());// 删除 index 处的节点linkedList.removeOfIndex(1);linkedList.removeOfIndex(6);linkedList.removeOfIndex(2);linkedList.display();System.out.println(linkedList.size());// 找到 val 第一次出现的位置System.out.println(linkedList.indexOf(2));System.out.println(linkedList.indexOf(8));// 找到val 最后一次出现的位置System.out.println(linkedList.lastOfIndex(2));System.out.println(linkedList.lastOfIndex(8));// 清空链表linkedList.clear();System.out.println(linkedList.size());}
}