数据结构--循环双链表实现、详解
本文共 18122 字，大约阅读时间需要 60 分钟。
双链表
双链表的插入和删除操作
在p节点之前插入值为x的节点
在p节点之后插入值为x的节点
双链表的删除操作
双链表节点
package pers.zhang.linearList;/** * @author zhang * @date 2020/1/15 - 11:06 * 双链表节点类 */public class DLinkNode{ //数据元素 public T data; //前驱节点 public DLinkNode pred; //后继节点 public DLinkNode next; //带参构造 public DLinkNode(T data, DLinkNode pred, DLinkNode next){ this.data = data; this.pred = pred; this.next = next; } public DLinkNode(){ this(null, null, null); } public DLinkNode(T data){ this(data, null, null); } //toString() public String toString(){ return this.data.toString(); }}
实现循环双链表
package pers.zhang.linearList;/** * @author zhang * @date 2020/1/15 - 11:21 * * 循环双链表 */public class CirDoublyLinkedListimplements LinearList { //头指针 public DLinkNode head; //默认构造，构造空循环链表 public CirDoublyLinkedList(){ this.head = new DLinkNode (); this.head.pred = head; this.head.next = head; } //由指定数组中的多个对象构造循环双链表，采用尾插入构造循环双链表 public CirDoublyLinkedList(T[] element){ this(); //创建空循环双链表，只有头结点 DLinkNode rear = this.head; for (int i = 0; i < element.length; i++){ rear.next = new DLinkNode (element[i], rear, this.head); //尾插入 rear = rear.next; } this.head.pred = rear; } //深拷贝构造方法，复制循环双链表 public CirDoublyLinkedList(CirDoublyLinkedList list){ this(); //创建空循环双链表，只有头结点 DLinkNode rear = this.head; for (DLinkNode p = list.head.next; p != list.head; p = p.next){ rear.next = new DLinkNode (p.data, rear, this.head); rear = rear.next; } this.head.pred = rear; } //深拷贝构造方法，由单链表list构造循环双链表 public CirDoublyLinkedList(SinglyLinkedList list){ this(); DLinkNode rear = this.head; for (Node p = list.head.next; p != null; p = p.next){ rear.next = new DLinkNode (p.data, rear, this.head); rear = rear.next; } this.head.pred = rear; } //深拷贝构造方法，由循环单链表list构造循环双链表 public CirDoublyLinkedList(CirSinglyLinkedList list){ this(); DLinkNode rear = this.head; for (Node p = list.head.next; p != list.head; p = p.next){ rear.next = new DLinkNode (p.data, rear, this.head); rear = rear.next; } this.head.pred = rear; } //判断循环双链表是否空 @Override public boolean isEmpty() { return head.next == head; } //返回表长 @Override public int length() { int i = 0; for(DLinkNode p = this.head.next; p != this.head; p = p.next) i++; return i; } //返回第i（≥0）个元素，若i<0或大于表长则返回null，O(n) @Override public T get(int i) { if(i >= 0){ DLinkNode p = this.head.next; for(int j = 0; p != null && j < i; j++) p = p.next; if(p != null) return p.data; } return null;//当i<0或大于表长时 } //设置第i（≥0）个元素值为x。若i<0或大于表长则抛出序号越界异常；若x==null，不操作。O(n) @Override public void set(int i, T x) { if(x == null) return; DLinkNode p = this.head.next; for(int j = 0; p != null && j < i; j++) p = p.next; if(i >= 0 && p != null) p.data = x; else throw new IndexOutOfBoundsException(i + ""); } //插入第i（≥0）个元素值为x。若x==null，不插入。 //若i<0，插入x作为第0个元素；若i大于表长，插入x作为最后一个元素。O(n) @Override public void insert(int i, T x) { if(x == null)//不能插入空对象 return; DLinkNode p = this.head; for(int j = 0; j < i && p.next != this.head; j++) p = p.next; DLinkNode q = new DLinkNode (x, p, p.next);//插入在p节点之后，包括头插入，中间插入 p.pred.next = q; p.next = q; } //在循环双链表最后添加结点，O(1) @Override public void append(T x) { if(x == null) return; DLinkNode q = new DLinkNode (x, head.pred, head); head.pred.next = q; head.pred = q; } //删除第i（≥0）个元素，返回被删除对象。若i<0或i大于表长，不删除，返回null。O(n) @Override public T remove(int i) { if(i >= 0){ DLinkNode p = this.head.next; for(int j = 0; p != head && j < i; j++) p = p.next; if(p != head){ T old = p.data; p.pred.next = p.next; p.next.pred = p.pred; return old; } } return null; //throw new IndexOutOfBoundsException(i + ""); } //删除循环双链表所有元素 @Override public void removeAll() { this.head.pred = head; this.head.next = head; } //返回循环双链表所有元素的描述字符串，循环双链表遍历算法，O(n) @Override public String toString(){ String str = "("; for (DLinkNode p = this.head.next; p != this.head; p = p.next){ str += p.data.toString(); if (p.next != this.head) str += ","; } return str+")"; //空表返回() } //比较两条循环双链表是否相等，覆盖Object类的equals(obj)方法 @Override public boolean equals(Object obj){ if (obj == this)//同一对象 return true; if (!(obj instanceof CirDoublyLinkedList))//不同类对象 return false; DLinkNode p = this.head.next; CirDoublyLinkedList list = (CirDoublyLinkedList )obj; DLinkNode q = list.head.next; while (p!=head && q!=list.head && p.data.equals(q.data)){ //逐个比较 p = p.next; q = q.next; } return p == head && q == list.head; } //顺序查找关键字为key元素，返回首次出现的元素，若查找不成功返回null //key可以只包含关键字数据项，由T类的equals()方法提供比较对象相等的依据 @Override public T search(T key) { if(key == null) return null; for(DLinkNode p = this.head.next; p != this.head; p = p.next) if(key.equals(p.data)) return p.data; return null; } //判断线性表是否包含关键字为key元素 public boolean contain(T key){ return this.search(key) != null; } //输出循环双链表，从后向前沿着前驱域 public void printPred(){ System.out.print("从后向前沿着前驱域遍历循环双链表，("); for (DLinkNode p = this.head.pred; p != this.head; p = p.pred) { System.out.print(p.data.toString()); if (p.pred != this.head) System.out.print(", "); } System.out.println(")"); //空表返回() } /** * 以下四个方法提供迭代遍历循环双链表方式 */ //返回循环双链表第一个结点（非头结点），O(1) public DLinkNode getFirst(){ if (this.head.next == head) return null; return this.head.next; } //返回p的后继结点，O(1) public DLinkNode getNext(DLinkNode p){ if (this.head.next == head || p == null) return null; return p.next; } //返回p的前驱结点，O(1) public DLinkNode getPred(DLinkNode p){ if (this.head.next == head || p == null || this.head.next == p) return null; return p.pred; } //返回循环双链表最后一个结点，O(1) public DLinkNode getLast(){ if (this.head.pred == head) return null; return this.head.pred; } /** * 子表操作 */ //将list循环双链表中所有结点链接在当前循环双链表之后，并设置list为空 public void concat(CirDoublyLinkedList list){ DLinkNode rear = head.pred; rear.next = list.head.next; list.head.next.pred = rear; rear = list.head.pred; rear.next = this.head; this.head.pred = rear; list.head.pred = list.head; list.head.next = list.head; } //返回从第i(≥0)个结点开始、长度为n(≥0)的子表（深拷贝） //若i<0或n<0，抛出异常；若i>表长或n=0，返回空链表；若n超长，返回至表尾的子表 public CirDoublyLinkedList sub(int i, int n){ if (i < 0) throw new IndexOutOfBoundsException(i+""); //抛出序号越界异常 if (n < 0) throw new IllegalArgumentException(i+""); //抛出无效参数异常 DLinkNode p = this.head.next; for (int j = 0; j < i && p != this.head; j++) //寻找子表首结点 p = p.next; //循环停止时，p指向第i结点。若i>表长，则p==this.head CirDoublyLinkedList list = new CirDoublyLinkedList ();//空循环双链表 DLinkNode rear = list.head; //复制子表到list链表rear结点之后 for (int j = 0; p != this.head && j < n; j++, p = p.next){ rear.next.pred = new DLinkNode (p.data, rear, list.head); rear.next = rear.next.pred; rear = rear.next; } return list; //返回对象引用 } //插入子表（深拷贝），将list循环双链表中的所有结点复制插入到当前循环双链表front结点之后 public void insert(DLinkNode front, CirDoublyLinkedList list){ for (DLinkNode q = list.head.next; q != list.head; q = q.next){ front.next.pred = new DLinkNode (q.data, front, front.next); front.next = front.next.pred; front = front.next; } } //插入子表（深拷贝），将list循环双链表中的所有结点复制插入到当前循环双链表第i个结点之前 public void insert(int i, CirDoublyLinkedList list){ DLinkNode p = this.head; for (int j = 0; j < i && p.next != this.head; j++) //寻找插入位置 p = p.next; //循环停止时，p指向第i-1结点或最后一个结点 this.insert(p,list); //复制插入list链表到p结点之后 } //将list循环双链表中所有结点复制添加到当前循环双链表最后 public void append(CirDoublyLinkedList list){ this.insert(this.head.pred, list); //复制插入list链表到链尾结点之后 } //删除从第i（≥0）个结点开始、长度为n（≥1）的子表 //若i<0或n<0，抛出异常；若i>表长或n=0，不删除；若n超长，删除至表尾的子表 //算法类似单链表 public void remove(int i, int n){ if (i < 0) throw new IndexOutOfBoundsException(i+""); //抛出序号越界异常 if (n < 0) throw new IllegalArgumentException(i+""); //抛出无效参数异常 DLinkNode front = this.head.next; for (int j = 0; j < i && front != this.head; j++) //寻找待删除子表首结点的前驱结点 front = front.next; if (front == this.head) //i越界，不删除 return; DLinkNode p = front.next; for (int j = 0; j < n && p != this.head; j++) //寻找待删除子表之后的结点 p = p.next; front.next = p; //删除front后继结点至p前驱结点之间的子表 p.pred = front; } //返回this单链表首个与patten匹配子表的首结点，查找不成功时返回null public DLinkNode index(CirDoublyLinkedList pattern){ return index(head.next, pattern); } //返回this单链表从start结点开始首个与pattern匹配子表的首结点，查找不成功时返回null，BF模式匹配 public DLinkNode index(DLinkNode start, CirDoublyLinkedList pattern){ if (start == null || pattern.isEmpty()) return null; DLinkNode p = start, q = pattern.head.next; while (p != this.head && q != pattern.head){ if (p.data.equals(q.data)){ //继续比较下一个结点 p = p.next; q = q.next; }else{ //回退 start = start.next; //目标表继续从下个子表 p = start; q = pattern.head.next; //模式表回退至表头 } } if(q == pattern.head) //存在匹配的子表 return start; //返回子表首结点地址 return null; } //删除所有与pattern匹配的子表。算法调用index(pattern)查找到再删除。 public void removeAll(CirDoublyLinkedList pattern){ System.out.print("将" + this.toString() + "中" + pattern.toString() + "全部删除"); DLinkNode p = this.index(pattern); //返回从头结点开始首个与pattern匹配子表的首结点 //若pattern为空，返回null while (p != null){ DLinkNode q = pattern.head.next; while (q != pattern.head){ //删除从p开始与pattern匹配的子表。不能调用remove(i,n)方法，效率低 p.pred.next = p.next; //删除p结点，但未释放p结点，p.next和p.pred仍然有效 p.next.pred = p.pred; p = p.next; //p指向被删除结点的原后继结点 q = q.next; } p = this.index(p,pattern); //再次匹配，返回从p结点开始首个与pattern匹配子表的首结点 } System.out.println("的结果是" + this.toString()); } //将this单链表中首个与pattern匹配的子表替换为dest子表。 //算法类似replaceAll(pattern, dest)，只将while改为if，只做一次匹配替换 public void replaceFirst(CirDoublyLinkedList pattern, CirDoublyLinkedList dest){ System.out.print("将" + this.toString() + "中首个" + pattern.toString() + "替换为" + dest.toString()); DLinkNode p = this.index(pattern); //返回从头开始首个与pattern匹配子表的首结点 if (p != null){ //匹配成功，进行替换 DLinkNode q = pattern.head.next; while (q != pattern.head){ //删除从p开始与pattern匹配的子表 p.pred.next = p.next; //删除p结点，但未释放p结点，p.next和p.pred仍然有效 p.next.pred = p.pred; p = p.next; q = q.next; } p = p.pred; q = dest.head.next; while (q!=dest.head){ //将dest中所有结点深拷贝插入到当前单链表p结点之后 p.next.pred = new DLinkNode (q.data,p,p.next); //将q结点深拷贝插入到p结点之后 p.next = p.next.pred; p = p.next; q = q.next; } p = p.next; } System.out.println("的结果是" + this.toString()); } //将this单链表中所有与pattern匹配的子表替换为dest子表。 //算法调用index(pattern)查找到再删除和插入。 public void replaceAll(CirDoublyLinkedList pattern, CirDoublyLinkedList dest){ System.out.print("将" + this.toString() + "中" + pattern.toString() + "全部替换为" + dest.toString()); DLinkNode p = this.index(pattern); //返回从头开始首个与pattern匹配子表的首结点 while (p != null){ //匹配成功，进行一次替换 DLinkNode q = pattern.head.next; while (q != pattern.head) //删除从p开始与pattern匹配的子表 { p.pred.next = p.next; //删除p结点，但未释放p结点，p.next和p.pred仍然有效 p.next.pred = p.pred; p = p.next; q = q.next; } p = p.pred; q = dest.head.next; while (q != dest.head){ //将dest中所有结点深拷贝插入到当前单链表p结点之后 p.next.pred = new DLinkNode (q.data,p,p.next); //将q结点深拷贝插入到p结点之后 p.next = p.next.pred; p = p.next; q = q.next; } p = p.next; p = this.index(p,pattern); //再次匹配，返回从p结点开始首个与pattern匹配子表的首结点 } System.out.println("的结果是" + this.toString()); } //删除所有与pattern匹配的子表。BF模式匹配算法查找到再删除，没有调用index(pattern)。算法同单链表。// public void removeAll(CirDoublyLinkedList pattern)// { // System.out.print("将"+this.toString()+"中"+pattern.toString()+"全部删除");// if (pattern.isEmpty()) //若无此句，则死循环，错误// return;// DLinkNode start=this.head.next;// while (start!=this.head)// { // DLinkNode p=start, q=pattern.head.next;// while (p!=this.head && q!=pattern.head && p.data.equals(q.data)) //一次匹配// { p=p.next;// q=q.next;// }// if (q!=pattern.head) //匹配失败，进行下次匹配// start=start.next;// else //匹配成功，删除该匹配子表// { start.pred.next = p;// p.pred = start.pred;// start=p;// }// }// System.out.println("的结果是"+this.toString());// } //将this单链表中所有与pattern匹配的子表替换为dest子表。当dest为空时，相当于删除匹配子表。 //包含BF模式匹配、删除匹配子表、复制插入子表算法// public void replaceAll(CirDoublyLinkedList pattern, CirDoublyLinkedList dest)// { // System.out.print("将"+this.toString()+"中"+pattern.toString()+"全部替换为"+dest.toString()+"的结果是");// if (pattern.isEmpty()) //若无此句，则将dest插入到start结点之后，错误// return;// DLinkNode start=this.head.next;// while (start!=this.head) //start指向每次匹配的起始结点// { // DLinkNode p=start, q=pattern.head.next;// while (p!=this.head && q!=pattern.head && p.data.equals(q.data))//一次匹配的多次比较// { p=p.next;// q=q.next;// }// if (q!=pattern.head) //匹配失败，进行下次匹配// start=start.next;// else //匹配成功，替换该匹配子表// { start.pred.next = p; //删除该匹配子表// p.pred = start.pred;// start=p;// DLinkNode d=dest.head.next;// while (d!=dest.head) //将dest剩余结点深拷贝插入到this单链表p之前// { DLinkNode t = new DLinkNode (d.data, p.pred, p);// p.pred.next = t;// p.pred = t;// d = d.next;// }// }// }// System.out.println(this.toString());// } /** * 实现迭代器 */ public java.util.Iterator iterator(){ return new DoublyIterator(); } //私有内部类实现迭代器 private class DoublyIterator implements java.util.Iterator { //当前节点 DLinkNode current = CirDoublyLinkedList.this.head; //是否可删除状态 boolean removable = false; @Override public boolean hasNext() { return this.current.next != CirDoublyLinkedList.this.head; } @Override public T next() { if(this.hasNext()){ this.removable = true; this.current = this.current.next; return this.current.data; }else{ throw new java.util.NoSuchElementException(); } } @Override public void remove() { if(this.removable){ this.current.next.pred = this.current.pred; this.current.pred.next = this.current.next; this.current = this.current.pred; this.removable = false; }else{ throw new java.lang.IllegalStateException(); } } } public java.util.ListIterator listIterator(){ //返回Java列表迭代器对象 return new DoublyListIterator(0); } public java.util.ListIterator listIterator(final int index){ //返回Java列表迭代器对象 return new DoublyListIterator(index); } //私有内部类，实现列表迭代器接口 private class DoublyListIterator extends DoublyIterator implements java.util.ListIterator { //当前元素序号 int succ = 0; public DoublyListIterator(int index){ this.succ = index; // current=CirDoublyLinkedList.this.head;//当前结点 int i = -1; while (i < index && this.hasNext()){ i++; this.current = this.current.next; } if (index < 0 || !this.hasNext()) throw new IndexOutOfBoundsException("Index: " + index); } public boolean hasPrevious(){ //若有前驱元素，返回true return this.current.pred != CirDoublyLinkedList.this.head; } public T previous(){ //返回前驱元素 if (this.hasPrevious()){ this.current = this.current.pred; this.succ--; return this.current.data; }else{ throw new java.util.NoSuchElementException(); //抛出无此元素异常 } } //返回后继元素序号 public int nextIndex(){ return this.succ; } //返回前驱元素序号 public int previousIndex(){ return this.succ-1; } //将集合当前元素替换为x public void set(T x){ if (x != null && this.current != CirDoublyLinkedList.this.head) this.current.data = x; } //增加元素x，在当前结点之后插入x public void add(T x){ if (x == null) return; //不能添加空对象 DLinkNode q = new DLinkNode (x, this.current, this.current.next); this.current.next.pred = q; //在当前结点之后插入x this.current.next = q; this.current = this.current.next; this.succ++; //插入结点为当前结点 } }}
测试：
package pers.zhang.linearList;import java.util.Iterator;/** * @author zhang * @date 2020/1/15 - 15:13 */public class DoublyLinkedList_ex { public static Integer[] random(int n) //返回产生n个随机数的数组 { Integer[] elements = new Integer[n]; for (int i=0; i list1 = new CirDoublyLinkedList (random(5)); System.out.print("list1: "+list1.toString()+"，"); list1.printPrevious(); list1.insert(-1, -1); //插入位置容错 list1.insert(0, 0); list1.insert(6, 6); list1.insert(100, 100); //插入位置容错 list1.set(3, new Integer((int)(list1.get(3).intValue()+100))); System.out.println("插入后: "+list1.toString()); list1.remove(0); list1.remove(3); list1.remove(100); //序号越界，没删除 System.out.println("删除后: "+list1.toString()); CirDoublyLinkedList list2 = new CirDoublyLinkedList (list1);//深拷贝 System.out.println("list2: "+list2.toString()); //习题2/* SinglyLinkedList list3 = new SinglyLinkedList (random(9));//单链表 System.out.println("list3: "+list3.toString()); CirDoublyLinkedList list4 = new CirDoublyLinkedList (list3);//由单链表构造循环双链表 System.out.println("list4: "+list4.toString()); CirSinglyLinkedList list5 = new CirSinglyLinkedList (random(9));//循环单链表 System.out.println("list5: "+list5.toString()); CirDoublyLinkedList list6 = new CirDoublyLinkedList (list5);//由循环单链表构造循环双链表 System.out.println("list6: "+list6.toString()); list6.printPrevious();*/ //深拷贝与比较相等 CirDoublyLinkedList list1 = new CirDoublyLinkedList (); //空表 System.out.println("list1: "+list1.toString()); CirDoublyLinkedList list2 = new CirDoublyLinkedList (); //空表 System.out.println("list2: "+list2.toString()); System.out.println("list1.equals(list2)? "+list1.equals(list2)); list1 = new CirDoublyLinkedList (random(5)); System.out.println("list1: "+list1.toString()); list2 = new CirDoublyLinkedList (list1); //拷贝构造方法 System.out.println("list2: "+list2.toString()); System.out.println("list1.equals(list2)? "+list1.equals(list2)); System.out.println("list1: "+list1.toString()); list2.set(0, new Integer(list1.get(0).intValue()+100)); list2.remove(list2.length()-1); System.out.println("list2: "+list2.toString()); System.out.println("list1.equals(list2)? "+list1.equals(list2)); //10.2 实现迭代器 Iterator it = list1.iterator(); //获得单链表迭代器对象 int sum=0; while (it.hasNext()) { int value=it.next().intValue(); sum += value; System.out.print(value); if (it.hasNext()) System.out.print("+"); } System.out.println("="+sum); }} 输出：
list1: (91, 16, 6, 5, 74)(74, 5, 6, 16, 91)插入后: (0, -1, 91, 116, 6, 5, 6, 74, 100)删除后: (-1, 91, 116, 5, 6, 74, 100)list2: (-1, 91, 116, 5, 6, 74, 100)list3: (17, 66, 48, 19, 17, 33, 46, 60, 65)list4: (17, 66, 48, 19, 17, 33, 46, 60, 65)list5: (97, 67, 25, 31, 48, 97, 1, 58, 10)list6: (97, 67, 25, 31, 48, 97, 1, 58, 10)(10, 58, 1, 97, 48, 31, 25, 67, 97) //深拷贝与比较相等list1: ()list2: ()list1.equals(list2)? truelist1: (21, 80, 7, 47, 44)list2: (21, 80, 7, 47, 44)list1.equals(list2)? truelist1: (21, 80, 7, 47, 44)list2: (121, 80, 7, 47)list1.equals(list2)? false21+80+7+47+44=199
转载地址：http://zypqb.baihongyu.com/
你可能感兴趣的文章
Plover.io在本地设备之间快速共享文件
查看>>
如何在OS X照片中禁用iCloud照片同步
查看>>
Minecraft的官方网站分发了受恶意软件感染的皮肤
查看>>
如何组织您的iPhone主屏幕
查看>>
如何使用Odin手动更新三星手机
查看>>
word模板快速填内容_如何快速轻松地在Word中选择内容块
查看>>
如何在Word 2013中直接从一个表导航到另一个表
查看>>
twitch 录像_如何通过NVIDIA GeForce Experience将您的PC游戏玩法传送到Twitch
查看>>
linux gnome_在Gnome中学习这些鼠标技巧，以获得更高效的Linux体验
查看>>
打印机疑难解答_使用内置电源疑难解答改善Windows 7中的电池寿命
查看>>
下载spotify音乐_完成播放列表或专辑后如何停止Spotify停止自动播放音乐
查看>>
nest keyword_PSA：如果您的Nest Cam没有启用2FA，则黑客可能会监视您
查看>>
drupal加密_立即更新您的Drupal网站，否则黑客可能将其变成加密货币矿工
查看>>
vimrc配置 鼠标光标_在“提示”框中：即时调整窗口大小，包含鼠标光标并了解电池配置...
查看>>
询问HTG：安装XBMC附加组件，缩小视频以进行移动播放，自动更改默认打印机
查看>>
High Sierra推出后如何离开macOS公开Beta
查看>>
如何格式化您的WhatsApp消息
查看>>
pixel2pixel_Pixel 2的视觉核心是什么？
查看>>
更改用户账户设置自动更改_您应该更改的5个SimpliSafe设置
查看>>
excel中转换为数值_如何在Microsoft Excel中转换货币
查看>>