Java模拟单链表和双端链表数据结构的实例讲解

/**  * 单链表:头插法 后进先出  * 将链表的左边称为链头，右边称为链尾。  * 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。  * 头插法最先得到的是尾结点  * @author stone  */ public class SingleLinkedList<T> {      private Link<T> first;    //首结点   public SingleLinkedList() {        }      public boolean isEmpty() {     return first == null;   }      public void insertFirst(T data) {// 插入 到 链头     Link<T> newLink = new Link<T>(data);     newLink.next = first; //新结点的next指向上一结点     first = newLink;   }      public Link<T> deleteFirst() {//删除 链头     Link<T> temp = first;     first = first.next; //变更首结点，为下一结点     return temp;   }      public Link<T> find(T t) {     Link<T> find = first;     while (find != null) {       if (!find.data.equals(t)) {         find = find.next;       } else {         break;       }     }     return find;   }      public Link<T> delete(T t) {     if (isEmpty()) {       return null;     } else {       if (first.data.equals(t)) {         Link<T> temp = first;         first = first.next; //变更首结点，为下一结点         return temp;       }     }     Link<T> p = first;     Link<T> q = first;     while (!p.data.equals(t)) {       if (p.next == null) {//表示到链尾还没找到         return null;       } else {         q = p;         p = p.next;       }     }          q.next = p.next;     return p;   }      public void displayList() {//遍历     System.out.println("List (first-->last):");     Link<T> current = first;     while (current != null) {       current.displayLink();       current = current.next;     }   }      public void displayListReverse() {//反序遍历     Link<T> p = first, q = first.next, t;     while (q != null) {//指针反向，遍历的数据顺序向后       t = q.next; //no3       if (p == first) {// 当为原来的头时，头的.next应该置空         p.next = null;       }       q.next = p;// no3 -> no1 pointer reverse       p = q; //start is reverse       q = t; //no3 start     }     //上面循环中的if里，把first.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给first     first = p;      displayList();   }      class Link<T> {//链结点     T data;   //数据域     Link<T> next; //后继指针，结点    链域     Link(T data) {       this.data = data;     }     void displayLink() {       System.out.println("the data is " + data.toString());     }   }      public static void main(String[] args) {     SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();     list.insertFirst(33);     list.insertFirst(78);     list.insertFirst(24);     list.insertFirst(22);     list.insertFirst(56);     list.displayList();          list.deleteFirst();     list.displayList();          System.out.println("find:" + list.find(56));     System.out.println("find:" + list.find(33));          System.out.println("delete find:" + list.delete(99));     System.out.println("delete find:" + list.delete(24));     list.displayList();     System.out.println("----reverse----");     list.displayListReverse();   } } 

List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList$Link@17dfafd1 List (first-->last): the data is 22 the data is 78 the data is 33 ----reverse---- List (first-->last): the data is 33 the data is 78 the data is 22 

单链表:尾插法 、后进先出 ――若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。 
尾插法建立链表时，头指针固定不动，故必须设立一个尾部的指针，向链表右边延伸， 
尾插法最先得到的是头结点。 

public class SingleLinkedList2<T> {      private Link<T> head;   //首结点   public SingleLinkedList2() {        }      public boolean isEmpty() {     return head == null;   }      public void insertLast(T data) {//在链尾 插入     Link<T> newLink = new Link<T>(data);     if (head != null) {       Link<T> nextP = head.next;       if (nextP == null) {         head.next = newLink;       } else {         Link<T> rear = null;         while (nextP != null) {           rear = nextP;           nextP = nextP.next;         }         rear.next = newLink;       }     } else {       head = newLink;     }   }      public Link<T> deleteLast() {//删除 链尾     Link<T> p = head;     Link<T> q = head;     while (p.next != null) {// p的下一个结点不为空，q等于当前的p(即q是上一个，p是下一个) 循环结束时，q等于链尾倒数第二个       q = p;       p = p.next;     }     //delete     q.next = null;     return p;   }      public Link<T> find(T t) {     Link<T> find = head;     while (find != null) {       if (!find.data.equals(t)) {         find = find.next;       } else {         break;       }     }     return find;   }      public Link<T> delete(T t) {     if (isEmpty()) {       return null;     } else {       if (head.data.equals(t)) {         Link<T> temp = head;         head = head.next; //变更首结点，为下一结点         return temp;       }     }     Link<T> p = head;     Link<T> q = head;     while (!p.data.equals(t)) {       if (p.next == null) {//表示到链尾还没找到         return null;       } else {         q = p;         p = p.next;       }     }          q.next = p.next;     return p;   }      public void displayList() {//遍历     System.out.println("List (head-->last):");     Link<T> current = head;     while (current != null) {       current.displayLink();       current = current.next;     }   }      public void displayListReverse() {//反序遍历     Link<T> p = head, q = head.next, t;     while (q != null) {//指针反向，遍历的数据顺序向后       t = q.next; //no3       if (p == head) {// 当为原来的头时，头的.next应该置空         p.next = null;       }       q.next = p;// no3 -> no1 pointer reverse       p = q; //start is reverse       q = t; //no3 start     }     //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head     head = p;      displayList();   }      class Link<T> {//链结点     T data;   //数据域     Link<T> next; //后继指针，结点    链域     Link(T data) {       this.data = data;     }     void displayLink() {       System.out.println("the data is " + data.toString());     }   }      public static void main(String[] args) {     SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>();     list.insertLast(33);     list.insertLast(78);     list.insertLast(24);     list.insertLast(22);     list.insertLast(56);     list.displayList();          list.deleteLast();     list.displayList();          System.out.println("find:" + list.find(56));     System.out.println("find:" + list.find(33));          System.out.println("delete find:" + list.delete(99));     System.out.println("delete find:" + list.delete(78));     list.displayList();     System.out.println("----reverse----");     list.displayListReverse();   } } 

List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 the data is 56 List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 find:null find:linked_list.SingleLinkedList2$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList2$Link@17dfafd1 List (head-->last): the data is 33 the data is 24 the data is 22 ----reverse---- List (head-->last): the data is 22 the data is 24 the data is 33 

/**  * 双端链表  * @author stone  */ public class TwoEndpointList<T> {   private Link<T> head;   //首结点   private Link<T> rear;   //尾部指针      public TwoEndpointList() {        }      public T peekHead() {     if (head != null) {       return head.data;     }     return null;   }      public boolean isEmpty() {     return head == null;   }      public void insertFirst(T data) {// 插入 到 链头     Link<T> newLink = new Link<T>(data);     newLink.next = head; //新结点的next指向上一结点     head = newLink;   }      public void insertLast(T data) {//在链尾 插入     Link<T> newLink = new Link<T>(data);     if (head == null) {       rear = null;     }     if (rear != null) {       rear.next = newLink;     } else {       head = newLink;       head.next = rear;     }     rear = newLink; //下次插入时，从rear处插入        }      public T deleteHead() {//删除 链头     if (isEmpty()) return null;     Link<T> temp = head;     head = head.next; //变更首结点，为下一结点     if (head == null) {     <span style="white-space:pre">  </span>rear = head;     }     return temp.data;   }      public T find(T t) {     if (isEmpty()) {       return null;     }     Link<T> find = head;     while (find != null) {       if (!find.data.equals(t)) {         find = find.next;       } else {         break;       }     }     if (find == null) {       return null;     }     return find.data;   }      public T delete(T t) {     if (isEmpty()) {       return null;     } else {       if (head.data.equals(t)) {         Link<T> temp = head;         head = head.next; //变更首结点，为下一结点         return temp.data;       }     }     Link<T> p = head;     Link<T> q = head;     while (!p.data.equals(t)) {       if (p.next == null) {//表示到链尾还没找到         return null;       } else {         q = p;         p = p.next;       }     }     q.next = p.next;     return p.data;   }      public void displayList() {//遍历     System.out.println("List (head-->last):");     Link<T> current = head;     while (current != null) {       current.displayLink();       current = current.next;     }   }      public void displayListReverse() {//反序遍历     if (isEmpty()) {       return;     }     Link<T> p = head, q = head.next, t;     while (q != null) {//指针反向，遍历的数据顺序向后       t = q.next; //no3       if (p == head) {// 当为原来的头时，头的.next应该置空         p.next = null;       }       q.next = p;// no3 -> no1 pointer reverse       p = q; //start is reverse       q = t; //no3 start     }     //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head     head = p;      displayList();   }      class Link<T> {//链结点     T data;   //数据域     Link<T> next; //后继指针，结点    链域     Link(T data) {       this.data = data;     }     void displayLink() {       System.out.println("the data is " + data.toString());     }   }      public static void main(String[] args) {     TwoEndpointList<Integer> list = new TwoEndpointList<Integer>();     list.insertLast(1);     list.insertFirst(2);     list.insertLast(3);     list.insertFirst(4);     list.insertLast(5);     list.displayList();          list.deleteHead();     list.displayList();          System.out.println("find:" + list.find(6));     System.out.println("find:" + list.find(3));      System.out.println("delete find:" + list.delete(6));     System.out.println("delete find:" + list.delete(5));     list.displayList();     System.out.println("----reverse----");     list.displayListReverse();   } } 

List (head-->last): the data is 4 the data is 2 the data is 1 the data is 3 the data is 5 List (head-->last): the data is 2 the data is 1 the data is 3 the data is 5 find:null find:3 delete find:null delete find:5 List (head-->last): the data is 2 the data is 1 the data is 3 ----reverse---- List (head-->last): the data is 3 the data is 1 the data is 2 

public class LinkStack<T> {   private TwoEndpointList<T> datas;      public LinkStack() {     datas = new TwoEndpointList<T>();   }      // 入栈   public void push(T data) {     datas.insertFirst(data);   }      // 出栈   public T pop() {     return datas.deleteHead();   }      // 查看栈顶   public T peek() {     return datas.peekHead();   }      //栈是否为空   public boolean isEmpty() {     return datas.isEmpty();   }      public static void main(String[] args) {     LinkStack<Integer> stack = new LinkStack<Integer>();     for (int i = 0; i < 5; i++) {       stack.push(i);     }     for (int i = 0; i < 5; i++) {       Integer peek = stack.peek();       System.out.println("peek:" + peek);     }     for (int i = 0; i < 6; i++) {       Integer pop = stack.pop();       System.out.println("pop:" + pop);     }          System.out.println("----");     for (int i = 5; i > 0; i--) {       stack.push(i);     }     for (int i = 5; i > 0; i--) {       Integer peek = stack.peek();       System.out.println("peek:" + peek);     }     for (int i = 5; i > 0; i--) {       Integer pop = stack.pop();       System.out.println("pop:" + pop);     }   } } 

peek:4 peek:4 peek:4 peek:4 peek:4 pop:4 pop:3 pop:2 pop:1 pop:0 pop:null ---- peek:1 peek:1 peek:1 peek:1 peek:1 pop:1 pop:2 pop:3 pop:4 pop:5 

public class LinkQueue<T> {   private TwoEndpointList<T> list;      public LinkQueue() {     list = new TwoEndpointList<T>();   }   //插入队尾   public void insert(T data) {     list.insertLast(data);   }   //移除队头   public T remove() {     return list.deleteHead();   }   //查看队头   public T peek() {     return list.peekHead();   }      public boolean isEmpty() {     return list.isEmpty();   }      public static void main(String[] args) {     LinkQueue<Integer> queue = new LinkQueue<Integer>();     for (int i = 1; i < 5; i++) {       queue.insert(i);     }     for (int i = 1; i < 5; i++) {       Integer peek = queue.peek();       System.out.println("peek:" + peek);     }     for (int i = 1; i < 5; i++) {       Integer remove = queue.remove();       System.out.println("remove:" + remove);     }          System.out.println("----");          for (int i = 5; i > 0; i--) {       queue.insert(i);     }     for (int i = 5; i > 0; i--) {       Integer peek = queue.peek();       System.out.println("peek2:" + peek);     }     for (int i = 5; i > 0; i--) {       Integer remove = queue.remove();       System.out.println("remove:" + remove);     }   } } 

peek:1 peek:1 peek:1 peek:1 remove:1 remove:2 remove:3 remove:4 ---- peek2:5 peek2:5 peek2:5 peek2:5 peek2:5 remove:5 remove:4 remove:3 remove:2 remove:1