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

模拟单链表

线性表：
线性表（亦作顺序表）是最基本、最简单、也是最常用的一种数据结构。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
线性表的逻辑结构简单，便于实现和操作。
在实际应用中，线性表都是以栈、队列、字符串等特殊线性表的形式来使用的。
线性结构的基本特征为:
1．集合中必存在唯一的一个“第一元素”；
2．集合中必存在唯一的一个 “最后元素” ；
3．除最后一个元素之外，均有 唯一的后继(后件)；
4．除第一个元素之外，均有 唯一的前驱(前件)。

链表：linked list
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
每个数据项都被包含在“链结点”（link）中。
链结点是一个类的对象，这类可叫做link。链表中有许多类似的链结点，每个link中都中包含有一个对下一个链结点引用的字段next。
链表对象本身保存了一个指向第一个链结点的引用first。(若没有first，则无法定位)
链表不能像数组那样(利用下标)直接访问到数据项，而需要用数据间的关系来定位，即访问链结点所引用的下一个链结点，而后再下一个，直至访问到需要的数据
在链头插入和删除的时间复杂度为o(1)，因为只需要改变引用的指向即可
而查找、删除指定结点、在指定结点后插入，这些操作都需要平均都需要搜索链表中的一半结点，效率为o(n)。
单链表：
以“结点的序列”表示线性表 称作线性链表（单链表）
是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。(这组存储单元既可以是连续的，也可以是不连续的)
链结点的结构：

存放结点值的数据域data;存放结点的引用 的指针域（链域）next
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
每个结点只有一个链域的链表称为单链表（single linked list） ， 一个方向, 只有后继结节的引用

/** 
 * 单链表:头插法 后进先出 
 * 将链表的左边称为链头，右边称为链尾。 
 * 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。 
 * 头插法最先得到的是尾结点 
 * @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 

模拟双端链表，以链表实现栈和队列
双端链表：
双端链表与传统链表非常相似.只是新增了一个属性-即对最后一个链结点的引用rear
这样在链尾插入会变得非常容易，只需改变rear的next为新增的结点即可，而不需要循环搜索到最后一个节点
所以有insertfirst、insertlast
删除链头时，只需要改变引用指向即可；删除链尾时，需要将倒数第二个结点的next置空，
而没有一个引用是指向它的，所以还是需要循环来读取操作

/** 
 * 双端链表 
 * @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