双向链表

java实现双向链表

package com.scc.demo; public class MyLinkedList { private Node first;// 链表中第一个节点 private Node last;// 链表中最后一个节点 private int size;// 节点的数量 // 创链表中的每一个节点 class Node { Node prev;// 上一个节点对象 Node next;// 下一个节点对象 Object ele;// 当前节点 元素 // 添加一个构造方法可以节点时并赋值 public Node(Object ele) { this.ele = ele; } } // 添加数据的第一位 public void addFirst(Object ele) { Node node = new Node(ele);// 节点对象 // 如果当前节点是第一次添加(当前节点即是开头也是结尾) if (size == 0) { this.first = node; this.last = node; } else { // 新节点的下一位是原有的节点 node.next = this.first; // 把新增的节点作为原有节点之前的一个节点 // 即第一个节点 this.first.prev = node; // 需要开始节点更改 this.first = node; } size++; } // 添加最后一位 public void addLast(Object ele) { // 先创建节点 Node node = new Node(ele); if (size == 0) { this.first = node; this.last = node; } else { // 当前节点的下一位是新的节点 this.last.next = node; // 新节点的上一位是原有节点 node.prev = this.last; // 更新新节点为下一个节点 this.last = node; } } @Override public String toString() { if (size == 0) { return "[]"; } StringBuffer sbr = new StringBuffer(); // 获取第一个节点 sbr.append("["); for (int i = 0; i < size - 1; i++) { sbr.append(first.ele); if (i != size - 1) { sbr.append(","); } else { sbr.append("]"); } first = first.next;// 获取下一个节点 } return sbr.toString(); } // 删除节点 public void remove(Object ele) { // 找到要删除的节点 Node first = this.first; for (int i = 0; i < size; i++) { if (!first.ele.equals(ele)) { if (first.next == null) { return; } first = first.next; } } // 删除节点 if (first == this.first) { this.first = first.next; this.first.prev = null; } else if (first == last) { this.last = first.prev; this.last.next = null; } else { // 把删除节点的上一个节点连接删除节点的下一个节点 first.prev.next = first.next; // 把删除节点的下一个节点连接删除节点的上一个节点 first.next.prev = first.prev; } size--; } }