java实现双向链表
public class MLinkedList<T> { //元素个数 private int size = 0; //头指针 private Node<T> first; //尾指针 private Node<T> last; @Data @AllArgsConstructor static class Node<T> { private T data; private Node<T> next; private Node<T> prev; } /** * 在链表头部加入元素 * * @param t */ public void addFirst(T t) { Node<T> node = this.first; Node<T> newNode = new Node<>(t, node, null); first = newNode; //判断加入节点之前的链表是否为空 if (node == null) { last = newNode; } else { node.prev = newNode; } size++; } /** * 将数据加入到尾部 * * @param t */ public void addLast(T t) { Node<T> node = last; Node<T> newNode = new Node<>(t, null, node); last = newNode; if (node == null) { first = newNode; } else { node.next = newNode; } size++; } /** * 添加元素默认加到队尾 * * @param t */ public void add(T t) { addLast(t); } /** * 0 1 2 * 在指定位置更新元素为新值,索引需要在0~size-1之间 * * @param index * @param t */ public void set(int index, T t) { rangeCheck(index); int cursor = 0; Node<T> tNode = this.first; while (cursor != index) { tNode = tNode.next; cursor++; } //循环结束,现在cursor=index,tNode就是要更新的节点 tNode.data = t; } /** * insert不同于set,insert在指定位置插入节点,原来的节点后移 * @param index * @param t */ public void insert(int index,T t) { rangeCheck(index); if (index == 0) { addFirst(t); return; } int curIndex=0; Node<T> curNode = this.first; while (curIndex != index) { curNode=curNode.next; curIndex++; } Node<T> prev = curNode.prev; Node<T> newNode = new Node<>(t, curNode, prev); prev.next=newNode; curNode.prev=newNode; size++; } /** * 删除指定数据 * * @param t * @return */ public T remove(T t) { Node<T> tNode = this.first; while (tNode != null && !tNode.data.equals(t)) { tNode = tNode.next; } //走到这里可能是找到了,也可能到头了 if (tNode == null) { return null; } //如果tNode!=null,说明找到指定节点了 Node<T> prev = tNode.prev; Node<T> next = tNode.next; prev.next = next; next.prev = prev; size--; return t; } /** * 删除指定位置的数据 * @param i 索引 * @return */ public T removeAt(int i) { rangeCheck(i); int curIndex=0; Node<T> tNode = this.first; while (tNode != null && curIndex!=i) { tNode = tNode.next; curIndex++; } //走到这里可能是找到了,也可能到头了 if (tNode == null) { return null; } //如果tNode!=null,说明找到指定节点了 Node<T> prev = tNode.prev; Node<T> next = tNode.next; prev.next = next; next.prev = prev; size--; return tNode.data; } /** * 校验新增和删除元素的索引范围 * * @param index */ private void rangeCheck(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("下标越界"); } } /** * 搜索数据 * * @param x * @return */ public Node<T> search(T x) { Node<T> cursor = first; while (cursor != null && cursor.data != x) { cursor = cursor.next; } return cursor; } /** * 将链表转成数组 * * @return */ public Object[] toArray() { Object[] objects = new Object[size]; int count = 0; objects[count] = first.data; Node<T> cursor = first; while (cursor.next != null) { count++; cursor = cursor.next; objects[count] = cursor.data; } return objects; } @Override public String toString() { return Arrays.toString(toArray()); } public static void main(String[] args) { MLinkedList<Integer> MLinkedList = new MLinkedList<>(); MLinkedList.addLast(1); MLinkedList.addLast(2); MLinkedList.addLast(3); MLinkedList.addFirst(0); MLinkedList.addFirst(-1); MLinkedList.addFirst(-2); System.out.println(MLinkedList); MLinkedList.set(2, 100); System.out.println(MLinkedList); MLinkedList.remove(100); System.out.println(MLinkedList); MLinkedList.insert(4,400); System.out.println(MLinkedList); MLinkedList.insert(0,99); System.out.println(MLinkedList); MLinkedList.removeAt(3); System.out.println(MLinkedList); } }