单链表缺点:
仅存在后继,没有前驱,故只能正向遍历;
package dataStructureAtShangGuiGu;
public class DoubleLinkedListDemo {
public static void main(String[] args) throws InterruptedException {
Node1 node1 = new Node1(1,"节点1");
Node1 node2 = new Node1(2,"节点2");
Node1 node3 = new Node1(3,"节点3");
Node1 node4 = new Node1(4,"节点4");
sop("初始双向环形链表为:");
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.listForward();
/*
doubleLinkedList.add(node1);
doubleLinkedList.add(node2);
doubleLinkedList.add(node3);
doubleLinkedList.add(node4);
*/
doubleLinkedList.addByOrder(node4);
doubleLinkedList.addByOrder(node1);
doubleLinkedList.addByOrder(node3);
doubleLinkedList.addByOrder(node2);
sop("添加后链表情况:");
doubleLinkedList.listForward();
//doubleLinkedList.listReverse();
//sop("删除元素后情况:");
//doubleLinkedList.delete(3);
//doubleLinkedList.listForward();
//doubleLinkedList.listReverse();
sop("修改后链表情况:");
doubleLinkedList.update(new Node1(2,"被修改的节点编号2"));
doubleLinkedList.listForward();
}
private static void sop(Object obj) {
System.out.println(obj);
}
}
class DoubleLinkedList{
public Node1 head;
public Node1 tail;
public DoubleLinkedList(){
this.head = new Node1(-1,"");
this.tail = this.head;
}
public void add(Node1 node) {
Node1 cur = this.head;
if(-1==this.head.no) { //第一次添加节点,即初始化链表
this.head = node; //替换头节点
cur = this.head; //将辅助指针指向头节点
cur.next = cur; //将头节点next指向头节点
cur.pre = cur;
this.tail = cur;
this.head.no = node.no;
return;
}
Node1 tmp = null;
while(true) {
if(cur.next==this.head)
break;
cur = cur.next;
}
tmp = cur; //将当前指针位置存一起来以备接下来使用
cur.next = node; //将新节点连接到链表
cur = cur.next; //将指针指向新节点位置
cur.pre = tmp; //新节点pre指向链表连接前的最后一个节点
cur.next = this.head; //新节点next指向头节点
this.head.pre = cur; //头节点pre指向最后一个节点,到此环就建立起来了
this.tail = cur;
}
public void addByOrder(Node1 node) {
Node1 cur = this.head;
if(-1==this.head.no) { //第一次添加节点,即初始化链表
this.head = node; //替换头节点
cur = this.head; //将辅助指针指向头节点
cur.next = cur; //将头节点next指向头节点
cur.pre = cur;
this.tail = cur;
this.head.no = node.no;
return;
}
boolean flag = false;
while(true) {
if(node.no==cur.next.no) {
this.sop("已经存在该编号元素!无法插入");
return;
} //已经存在该编号元素,直接返回
if(cur.next==this.head) {
flag = true;
break;
}; //只有一个元素情况
if(node.no<=cur.next.no) break; //找到了插入的位置
cur = cur.next;
}
if(flag) { //添加初始的时候只有一个元素的情况
if(node.no<=cur.next.no) {
this.head = node;
this.head.next = cur;
this.head.pre = cur;
cur.next = this.head;
cur.pre = this.head;
}
}else {
Node1 curNext = cur.next;
node.pre = cur; //插入的元素的pre指向插入左边元素位置
node.next = cur.next; //插入的元素的next指向插入元素右边元素位置
cur.next = node; //插入的元素的左边元素的next指向插入的元素
curNext.pre = node;
}
Node1 cur1 = this.head;
while(cur1.next!=this.head) {
cur1 = cur1.next;
}
this.tail = cur1; //获取链表最后位置
}
public void delete(int no) {
Node1 cur = this.head;
if(-1==this.head.no) { //链表没有初始化的情况
sop("无法删除,链表是空的!");
return;
}
if(cur.next==this.head) { //元素只有一个情况
if(cur.no==no) { //只有一个元素且刚好匹配
this.head = new Node1(-1,"");
this.head.pre = this.head;
this.head.next = this.head;
this.tail = this.head;
return;
}
return;
}
while(true) {
if(cur.no==no) { //找到情况
cur.pre.next = cur.next;
cur.next.pre = cur.pre;
return;
}
cur = cur.next;
}
}
public void update(Node1 node) {
if(-1==this.head.no) { //链表没有初始化的情况
sop("无法修改,链表是空的!");
return;
}
Node1 cur = this.head;
while(true) {
if(cur.no==node.no) { //找到编号的情况
cur.name = node.name;
return;
}
cur = cur.next;
if(cur.no==node.no) { //找到编号的情况
cur.name = node.name;
return;
}
if(cur.next==this.head) {
return;
}
}
}
public void listForward() {
Node1 cur = this.head;
while(true){
if(-1==this.head.no) { //链表没有初始化的情况
sop("[]");
return;
}
sop("正:"+cur);
if(cur.next==this.head) return;
cur = cur.next;
}
}
public void listReverse() {
Node1 cur = this.tail;
while(true){
if(-1==this.head.no) { //链表没有初始化的情况
sop("[]");
return;
}
this.sop(cur);
if(cur.pre==this.tail) return;
cur = cur.pre;
}
}
public void listF() throws InterruptedException {
Node1 cur = this.head;
while(true){
sop("正: "+cur);
cur = cur.next;
Thread.sleep(500);
}
}
public void listR() throws InterruptedException {
Node1 cur = this.tail;
while(true){
sop("反: "+cur);
cur = cur.pre;
Thread.sleep(500);
}
}
private void sop(Object obj) {
System.out.println(obj);
}
}
class Node1{
public int no;
public String name;
public Node1 pre;
public Node1 next;
public Node1(int no,String name) {
this.no = no;
this.name = name;
}
public String toString() {
return "[no="+this.no+",name="+this.name+"]";
}
}