参考链接

前言

数组作为数据存储结构有一定的缺陷。在无序数组中，搜索性能差，在有序数组中，插入效率又很低，而且这两种数组的删除效率都很低，并且数组在创建后，其大小是固定了，设置的过大会造成内存的浪费，过小又不能满足数据量的存储。

　　本篇博客我们将讲解一种新型的数据结构——链表。我们知道数组是一种通用的数据结构，能用来实现栈、队列等很多数据结构。而链表也是一种使用广泛的通用数据结构，它也可以用来作为实现栈、队列等数据结构的基础，基本上除非需要频繁的通过下标来随机访问各个数据，否则很多使用数组的地方都可以用链表来代替。

　　但是我们需要说明的是，链表是不能解决数据存储的所有问题的，它也有它的优点和缺点。本篇博客我们介绍几种常见的链表，分别是单向链表、双端链表、有序链表、双向链表以及有迭代器的链表。并且会讲解一下抽象数据类型（ADT）的思想，如何用 ADT 描述栈和队列，如何用链表代替数组来实现栈和队列。

1、链表（Linked List）

　使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

2、单向链表（Single-Linked List）

　单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
　　单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。
链表 - 图1

1、单向链表的代码实现

  1. package datastrcrt;
  3. import datastrcrt.SingleLinkedList;
  5. public class SingleLinkedList {
  7.     private int size;//链表节点的个数
  8.     private Node head;//头节点
  9.     public SingleLinkedList()
  10.     {
  11.         size = 0;
  12.         head = null;
  13.     }
  14.     //链表的每个节点类
  15.     public class Node {
  16.         public Object data;
  17.         private Node next;
  18.         public Node(Object data)
  19.         {
  20.             this.data = data;
  21.         }
  23.     }
  24.     //在链表头添加元素
  25.     public void addhead(Object data)
  26.     {
  27.         Node newhead = new Node(data);
  28.         if(size == 0)
  29.         {
  30.             head = newhead;
  31.         }else
  32.         {
  33.             newhead.next = head;
  34.             head = newhead;
  35.         }
  36.         size++;
  37.     }
  38.     //在链表头删除元素
  39.     public Object delehead()
  40.     {
  41.         if(size == 0)
  42.         {
  43.             System.out.println("请先在链表中添加元素");
  44.             return null;
  45.         }
  46.         Object data = head.data;
  47.         head = head.next;
  48.         size--;
  49.         return data;
  50.     }
  51.     //查找指定的元素
  52.     public Node find(Object obj)
  53.     {
  54.         Node current = head;
  55.         if(size == 0)
  56.         {
  57.             System.out.println("请先在链表中添加元素");
  58.             return null;
  59.         }
  60.         while(current!=null)
  61.         {
  62.             if(current.data.equals(obj))
  63.             {
  64.                 return current;
  65.             }else
  66.             {
  67.                 current = current.next;
  68.             }            
  69.         }        
  70.         return null;    
  71.     }
  72.     //删除指定的元素
  73.     public Node delete(Object obj)
  74.     {
  75.         Node current = head;
  76.         Node precurrent = head;
  77.         while(current!=null)
  78.         {            
  79.             if(current.data.equals(obj)&&current.equals(head))
  80.             {
  82.                 head = current.next;
  83.                 size--;
  84.                 return current;
  85.             }else if(current.data.equals(obj)&&!current.equals(head))
  86.             {
  87.                 precurrent.next = current.next;
  88.                 size--;
  89.                 return current;
  90.             }        
  91.             precurrent = current;
  92.             current = current.next;
  94.         }        
  95.         return current;            
  96.     }
  97.     //判断链表是否为空
  98.     public boolean isEmpty()
  99.     {
  100.         return (size==0);
  101.     }
  102.     //显示节点信息
  103.     public void display()
  104.     {
  105.         if(size > 0)
  106.         {
  107.             Node node = head;
  108.             if(size == 1){//当前链表只有一个节点
  109.                   System.out.println("["+node.data+"]");
  110.                   return;
  111.             }
  112.             while(node!=null)
  113.             {
  114.                 if(node.equals(head))
  115.                 {
  116.                     System.out.print("["+node.data+"->");
  117.                 }else if(node.next == null)
  118.                 {
  119.                     System.out.print(node.data+"]");
  120.                 }else
  121.                 {
  122.                      System.out.print(node.data+"->");
  123.                 }
  124.                 node = node.next;
  125.             }
  126.             System.out.println();
  127.         }else
  128.         {
  129.             System.out.println("[]");
  130.         }
  131.     }
  133. }

2、用单向链表实现栈的代码实现

栈，线性表的一种特殊的存储结构。与学习过的线性表的不同之处在于栈只能从表的固定一端对数据进行插入和删除操作，另一端是封死的。
栈的pop()方法和push()方法，对应于链表的在头部删除元素deleteHead()以及在头部增加元素addHead()。
链表 - 图2

  1. public class StackSingleLink {
  2.     private SingleLinkedList link;
  4.     public StackSingleLink(){
  5.         link = new SingleLinkedList();
  6.     }
  8.     //添加元素
  9.     public void push(Object obj){
  10.         link.addHead(obj);
  11.     }
  13.     //移除栈顶元素
  14.     public Object pop(){
  15.         Object obj = link.deleteHead();
  16.         return obj;
  17.     }
  19.     //判断是否为空
  20.     public boolean isEmpty(){
  21.         return link.isEmpty();
  22.     }
  24.     //打印栈内元素信息
  25.     public void display(){
  26.         link.display();
  27.     }
  29. }

3、双端链表

对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。链表 - 图3

1、双端链表的代码实现

  1. package datastrcrt;
  3. import datastrcrt.SingleLinkedList;
  5. public class SingleLinkedList {
  7.     private int size;//链表节点的个数
  8.     private Node head;//头节点
  9.     private Node tail;//尾节点
  10.     public SingleLinkedList()
  11.     {
  12.         size = 0;
  13.         head = null;
  14.     }
  15.     //链表的每个节点类
  16.     public class Node {
  17.         public Object data;
  18.         private Node next;
  19.         public Node(Object data)
  20.         {
  21.             this.data = data;
  22.         }
  24.     }
  25.     //在链表头添加元素
  26.     public void addhead(Object data)
  27.     {
  28.         Node newhead = new Node(data);
  29.         if(size == 0)
  30.         {
  31.             head = newhead;
  32.             tail = newhead;
  33.         }else
  34.         {
  35.             newhead.next = head;
  36.             head = newhead;
  37.         }
  38.         size++;
  39.     }//在链表尾部添加元素
  40.     public void addtail(Object obj)
  41.     {
  42.         Node newtail = new Node(obj);
  43.         if(size == 0)
  44.         {
  45.             head = newtail;
  46.             tail = newtail;
  47.         }else
  48.         {
  49.             tail.next = newtail;
  50.             tail = newtail;
  51.         }
  52.         size++;
  53.     }
  54.     //在链表头删除元素
  55.     public Object delehead()
  56.     {
  57.         if(size == 0)
  58.         {
  59.             System.out.println("请先在链表中添加元素");
  60.             return null;
  61.         }
  62.         Object data = head.data;
  63.         head = head.next;
  64.         size--;
  65.         return data;
  66.     }
  67.     //查找指定的元素
  68.     public Node find(Object obj)
  69.     {
  70.         Node current = head;
  71.         if(size == 0)
  72.         {
  73.             System.out.println("请先在链表中添加元素");
  74.             return null;
  75.         }
  76.         while(current!=null)
  77.         {
  78.             if(current.data.equals(obj))
  79.             {
  80.                 return current;
  81.             }else
  82.             {
  83.                 current = current.next;
  84.             }            
  85.         }        
  86.         return null;    
  87.     }
  88.     //删除指定的元素
  89.     public Node delete(Object obj)
  90.     {
  91.         Node current = head;
  92.         Node precurrent = head;
  93.         while(current!=null)
  94.         {            
  95.             if(current.data.equals(obj)&&current.equals(head))
  96.             {
  98.                 head = current.next;
  99.                 size--;
  100.                 return current;
  101.             }else if(current.data.equals(obj)&&!current.equals(head))
  102.             {
  103.                 precurrent.next = current.next;
  104.                 size--;
  105.                 return current;
  106.             }        
  107.             precurrent = current;
  108.             current = current.next;
  110.         }        
  111.         return current;            
  112.     }
  113.     //判断链表是否为空
  114.     public boolean isEmpty()
  115.     {
  116.         return (size==0);
  117.     }
  118.     //获得链表的节点个数
  119.     public int getSize(){
  120.         return size;
  121.      }
  122.     //显示节点信息
  123.     public void display()
  124.     {
  125.         if(size > 0)
  126.         {
  127.             Node node = head;
  128.             if(size == 1){//当前链表只有一个节点
  129.                   System.out.println("["+node.data+"]");
  130.                   return;
  131.             }
  132.             while(node!=null)
  133.             {
  134.                 if(node.equals(head))
  135.                 {
  136.                     System.out.print("["+node.data+"->");
  137.                 }else if(node.next == null)
  138.                 {
  139.                     System.out.print(node.data+"]");
  140.                 }else
  141.                 {
  142.                      System.out.print(node.data+"->");
  143.                 }
  144.                 node = node.next;
  145.             }
  146.             System.out.println();
  147.         }else
  148.         {
  149.             System.out.println("[]");
  150.         }
  151.     }
  153. }

2、用双端链表实现队列的代码实现

  1. package com.ys.link;
  3. public class QueueLinkedList {
  5.     private DoublePointLinkedList dp;
  7.     public QueueLinkedList(){
  8.         dp = new DoublePointLinkedList();
  9.     }
  10.     public void insert(Object data){
  11.         dp.addTail(data);
  12.     }
  14.     public void delete(){
  15.         dp.deleteHead();
  16.     }
  18.     public boolean isEmpty(){
  19.         return dp.isEmpty();
  20.     }
  22.     public int getSize(){
  23.         return dp.getSize();
  24.     }
  26.     public void display(){
  27.         dp.display();
  28.     }
  30. }

四、双向链表

我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历。

链表 - 图4

1、双向链表的代码实现

  1. package datastrcrt;
  3. import datastrcrt.SingleLinkedList;
  5. public class SingleLinkedList {
  7.     private int size;//链表节点的个数
  8.     private Node head;//头节点
  9.     private Node tail;//尾节点
  10.     public SingleLinkedList()
  11.     {
  12.         size = 0;
  13.         head = null;
  14.     }
  15.     //链表的每个节点类
  16.     public class Node {
  17.         public Object data;
  18.         public Node next;
  19.         public Node prev;
  20.         public Node(Object data)
  21.         {
  22.             this.data = data;
  23.         }
  25.     }
  26.     //在链表头添加元素
  27.     public void addhead(Object data)
  28.     {
  29.         Node newhead = new Node(data);
  30.         if(size == 0)
  31.         {
  32.             head = newhead;
  33.             tail = newhead;
  34.         }else
  35.         {
  36.             head.prev = newhead;
  37.             newhead.next = head;
  38.             head = newhead;
  39.         }
  40.         size++;
  41.     }//在链表尾部添加元素
  42.     public void addtail(Object obj)
  43.     {
  44.         Node newtail = new Node(obj);
  45.         if(size == 0)
  46.         {
  47.             head = newtail;
  48.             tail = newtail;
  49.         }else
  50.         {
  51.             newtail.prev = tail;
  52.             tail.next = newtail;
  53.             tail = newtail;
  54.         }
  55.         size++;
  56.     }
  57.     //在链表头删除元素
  58.     public Object delehead()
  59.     {
  60.          Node temp = head;
  61.         if(size == 0)
  62.         {
  63.             System.out.println("请先在链表中添加元素");
  64.             return null;
  65.         }
  66.         head = head.next;
  67.         head.prev = null;
  68.         size--;
  69.         return temp;
  70.     }
  71.     //删除链表尾
  72.     public Node deleteTail()
  73.     {
  74.         Node temp = tail;
  75.         if(size == 0)
  76.         {
  77.             System.out.println("请先在链表中添加元素");
  78.             return null;
  79.         }
  80.         tail = tail.prev;
  81.         tail.next = null;
  82.         size--;
  83.         return temp;
  84.     }
  85.     //查找指定的元素
  86.     public Node find(Object obj)
  87.     {
  88.         Node current = head;
  89.         if(size == 0)
  90.         {
  91.             System.out.println("请先在链表中添加元素");
  92.             return null;
  93.         }
  94.         while(current!=null)
  95.         {
  96.             if(current.data.equals(obj))
  97.             {
  98.                 return current;
  99.             }else
  100.             {
  101.                 current = current.next;
  102.             }            
  103.         }        
  104.         return null;    
  105.     }
  106.     //删除指定的元素
  107.     public Node delete(Object obj)
  108.     {
  109.         Node current = head;
  110.         Node precurrent = head;
  111.         while(current!=null)
  112.         {            
  113.             if(current.data.equals(obj)&&current.equals(head))
  114.             {
  116.                 head = current.next;
  117.                 size--;
  118.                 return current;
  119.             }else if(current.data.equals(obj)&&!current.equals(head))
  120.             {
  121.                 precurrent.next = current.next;
  122.                 size--;
  123.                 return current;
  124.             }        
  125.             precurrent = current;
  126.             current = current.next;
  128.         }        
  129.         return current;            
  130.     }
  131.     //判断链表是否为空
  132.     public boolean isEmpty()
  133.     {
  134.         return (size==0);
  135.     }
  136.     //获得链表的节点个数
  137.     public int getSize(){
  138.         return size;
  139.      }
  140.     //显示节点信息
  141.     public void display()
  142.     {
  143.         if(size > 0)
  144.         {
  145.             Node node = head;
  146.             if(size == 1){//当前链表只有一个节点
  147.                   System.out.println("["+node.data+"]");
  148.                   return;
  149.             }
  150.             while(node!=null)
  151.             {
  152.                 if(node.equals(head))
  153.                 {
  154.                     System.out.print("["+node.data+"->");
  155.                 }else if(node.next == null)
  156.                 {
  157.                     System.out.print(node.data+"]");
  158.                 }else
  159.                 {
  160.                      System.out.print(node.data+"->");
  161.                 }
  162.                 node = node.next;
  163.             }
  164.             System.out.println();
  165.         }else
  166.         {
  167.             System.out.println("[]");
  168.         }
  169.     }
  171. }