双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
java模拟双链表结构.实现增删改查等方法.
/** * 双链表 */public class MyDoubleLink<T> implements Iterable<T>{ /** *节点的封装类 */ PRivate class Node{ Node prev;//上一个节点 T data;//数据 Node next;//下一个节点 } private Node head;//头节点 private Node rear;//尾节点 /** * 添加数据 * @param data */ public void add(T data){ //1.创建新的节点 Node node = new Node(); //2.把数据放入节点中 node.data = data; //3.把节点链接到链表中 //从链表的尾部添加数据 if (rear == null) { //说明链表是空,当前节点就成为头节点 rear = node; head = node; }else { //有头节点 rear.next = node; node.prev = rear; rear = node; } } /** * 重写toString方法 */ public String toString(){ StringBuffer sb = new StringBuffer("["); //遍历链表中的所有数据 Node node = head;//从头节点开始遍历数据 while (node != null) { //有数据 //拼接数据 //判断是否是尾节点 if (node != rear) { sb.append(node.data+", "); }else { sb.append(node.data); } //条件的改变 node = node.next; } sb.append("]"); return sb.toString(); } /** * 删除数据 * 1.只有一个数据 * 2.删除头节点 * 3.删除数据 * 4.删除尾节点 * @param data */ public void remove(T data){ //1.查找数据是否存在,查找数据所在的节点 Node node = findData(data); //2.判断node是否存在 if (node != null) { //存在 remove(node); } } /** * 删除节点 * @param node */ public void remove(Node node){ if (node == head && node == rear) { //1.只有一个数据 head = null; rear = null; }else if (node == head) { //2.删除头节点,后面肯定有节点 head = head.next; head.prev = null; }else if (node == rear) { //3.删除尾节点,前面肯定有节点 rear = rear.prev; rear.next = null; }else { //4.删除数据,前后肯定有节点 node.prev.next = node.next; node.next.prev = node.prev; } } /** * 查找数据所在节点 * @param data * @return */ private Node findData(T data) { Node node = head; while (node != null) { if (node.data.equals(data) && node.data.hashCode() == data.hashCode()) { //找到数据 break; }else { //继续下一个 node = node.next; } } return node; } /** * 修改数据 * @param oldData * @param newData */ public void updata(T oldData,T newData){ Node node = findData(oldData); if (node != null) { node.data = newData; } } /** * 修改数据(在对象的hash值相同的情况下修改对象属性值) * @param data */ public void updata(T data){ Node node = findData(data); if (node != null) { node.data = data; } } /** * 是否包含数据 * @param data * @return */ public boolean contains(T data){ return findData(data) != null; } /** * 重写迭代器方法,可以用增强for */ @Override public Iterator iterator() { class MyIte implements Iterator{ private Node node = head;//从头节点遍历 @Override public boolean hasNext() { return node != null; } @Override public Object next() { Object data = node.data;//获取数据 node = node.next;//设置下一个数据 return data; } @Override public void remove() { //删除next方法返回的数据 MyDoubleLink.this.remove(node.prev); } } return new MyIte(); } /** * 从头部添加数据 * @param data */ public void addFirst(T data){ //1.创建新的节点 Node node = new Node(); //2.把数据放入节点中 node.data = data; //3.把节点链接到链表中 //从链表的尾部添加数据 if (rear == null) { //说明链表是空,当前节点就成为头节点 rear = node; head = node; }else { //有头节点 head.prev = node; node.next = head; head = node; } } /** * 排序添加数据,添加数据时自动排序 * @param data */ public void addSort(T data){ addSortBlock(data,null); } /** * 查找比data大的第一个节点 * @param data * @return */ private Node findNext(T data){ //从头节点开始找 Node node = head; while (node != null) { //比较 if (compare(node.data, data)>0) { break; }else { //继续找下一个 node = node.next; } } return node; } /** * 查找比data大的第一个节点(使用比较器) * @param data * @param comp 比较器 * @return */ private Node findNext(T data,Comparator<T> comp){ //从头节点开始找 Node node = head; while (node != null) { //比较 if (comp.compare(node.data, data)>0) { break; }else { //继续找下一个 node = node.next; } } return node; } /** * 比较两个数据的大小 * @param obj1 * @param obj2 * @return * 0 相等 * 大于0 obj1 > obj2 * 小于0 obj1 < obj2 */ public int compare(T obj1,T obj2){ Comparable c1; Comparable c2; if (obj1 instanceof Comparable) { //数据实现比较器 c1 = (Comparable)obj1; c2 = (Comparable)obj2; }else { //没有实现比较器 c1 = obj1.toString(); c2 = obj2.toString(); } return c1.compareTo(c2); } /** * 添加数据并进行排序(使用比较器) * @param data * @param comparable 比较器 */ public void addSort(T data,Comparator<T> comparable){ addSortBlock(data,comparable); } /** * 添加数据并进行排序(私有方法) * @param data 传入数据 * @param comp 比较器 */ private void addSortBlock(T data,Comparator<T> comp){ //1.创建新的节点 Node node = new Node(); //2.把数据放入节点中 node.data = data; Node next = null; //2.找位置(从小到大)添加数据 if (comp != null) { next= findNext(data,comp); }else { next = findNext(data); } if (next != null) { //找到下一个节点,把data放到next节点前 if (next == head) { addFirst(data); }else { next.prev.next = node; node.next = next; node.prev = next.prev; next.prev = node; } }else { //没找到下一个节点,data最大 add(data); } }}新闻热点
疑难解答
