链表与顺序表

顺序表:

顺序表是用一组地址连续的存储单元来保存数据的，使用之前必须指定其长度，一但内存分配，不可动态改变大小。所以它具有随机存取，查找快速的特点，但是做插入或删除动作是，需要移动大量元素，效率较低。

长度固定，必须在分配内存之前确定数组的长度。
存储空间连续，即允许元素的随机访问。
存储密度大，内存中存储的全部是数据元素。
要访问特定元素，可以使用索引访问，时间复杂度为
要想在顺序表中插入或删除一个元素，都涉及到之后所有元素的移动，因此时间复杂度为

链表 :

链表，是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。每个数据结点单元有两部分组成，一个是数据域，存储数据值；另一个是指针域，指向下一个数据单元。

当多个结点通过指针指向，关联起来，就形成了一个链，即链表（java没有指针概念，指针是指对象，即结点）。

链表可分为单链表、双链表、循环链表。

单链表就是沿着单方向的链表。例如a->b->c->d… 只能顺序往下连接下去，即只可以从A往下找元素，但是反之则不行。

对比：

链表是线性表的链式存储结构，它相比于顺序表，在插入和删除元素时，效率要高很多。

数组线性表类ArrayList 和链表类LinkedList 是实现List接口的两个具体类。ArrayList 数组储存元素，这个数组是动态创建的。如果元素个数超过了数组的容量，就创建一个更大的新数组，并将当前所有元素都复制到新数组中。LinkedList在一个链表中储存元素。

如果需要通过下标来随机访问元素，但是除了在末尾处之外，不能在其他位置插入或删除元素，那么使用ArrayList更高效。

需要在线性表任意位置上插入或删除元素，就应该选择LinkedList。线性表的大小可动态增大或减小，但数组一旦被创建，大小就是固定的。如不需要在线性表中插入或删除元素，那么数组是效率最高的数据结构。

ArrayList是一个实现List接口的大小可变的数组，向ArrayList中添加元素，容量自动增大，但不能自动减小，需使用trimToSize（）将数组容量减小到线性表的大小

若要提取元素或者在线性表的尾部插入和删除元素，ArrayList的效率比较高，若要在线性表任意位置上插入和删除元素，LinkedList效率较高。

链表基本算法

插入结点

假设要在单链表的a结点和b结点之间插入一个值为x的新结点。

如下图所示，指针s指向一个值为x的结点，为了插入s。

首先让s的next指针指向b，即s->next = p->next;

然后，让a的next指针指向s，即p->next = s;

删除结点

假设要删除单链表中的b结点。

首先，找到b结点前面的结点a。

如下图所示，p指针指向a结点。b的下一个结点就是p->next->next。

所以，只要让p的next指针跳过b结点，指向b的下一个结点就OK了，即p->next = p->next->next;

链表代码实现

 1 package structure.link;
 2 /**
 3  * 
 4  * Description: 定义结点
 5  * @author 
 6  */
 7 public class Node {
 8     protected Node next;// 指针
 9     protected int data;// 数据数值
10 
11     public Node(int data) {
12         this.data = data;
13     }
14 
15     // 显示
16     public void display() {
17         System.out.print(data + " ");
18     }
19 
20 }

  1 package structure.link;
  2 /**
  3  * 
  4  * Description: LinkList方法
  5  * @author 
  6  */
  7 public class LinkList {
  8     private Node first; // 头节点
  9     private int pos = 0; // 节点位置
 10 
 11     public LinkList() {
 12         this.first = null;
 13 
 14     }
 15 
 16     // 插入一个头节点
 17     public void addFirstNode(int data) {
 18         Node node = new Node(data);
 19         node.next = first;
 20         first = node;
 21     }
 22 
 23     // 删除一个头结点,并返回头结点
 24     public Node deleteFirstNode() {
 25         Node tempNode = first;
 26         first = tempNode.next;
 27         return tempNode;
 28     }
 29 
 30     // 在任意位置插入节点 在index的后面插入 (插入在原链表index之前)
 31     public void add(int index, int data) {
 32         Node node = new Node(data);
 33         Node current = first; // 现在的
 34         Node previous = first; // 之前的（现在的前一个）
 35 
 36         while (index != pos++) {
 37             previous = current;
 38             current = current.next;
 39         }
 40         node.next = current;
 41         previous.next = node;
 42         pos = 0;
 43     }
 44 
 45     // 删除任意位置的节点
 46     public Node deleteByPos(int index) {
 47         Node current = first; // 现在的
 48         Node previous = first; // 之前的（现在的前一个）
 49         while (index != pos++) {
 50             if (current.next == null) {
 51                 break;
 52             }
 53             previous = current;
 54             current = current.next;
 55         }
 56         if (current == previous) {
 57             first = first.next;
 58         } else {
 59             previous.next = current.next;
 60             pos = 0;
 61         }
 62         return current;
 63     }
 64 
 65     // 根据节点的data删除节点(仅仅删除第一个)
 66     public Node deleteByData(int data) {
 67         Node current = first;
 68         Node previous = first;
 69         while (data != current.data) {
 70             if (current.next == null) {
 71                 break;
 72             }
 73             previous = current;
 74             current = current.next;
 75         }
 76         if (current.data == data) {
 77             first = first.next;
 78         } else {
 79             previous.next = current.next;
 80         }
 81         return current;
 82     }
 83 
 84     // 显示出所有的节点信息
 85     public void displayAllNodes() {
 86         Node current = first;
 87         while (current != null) {
 88             current.display();
 89             current = current.next;
 90         }
 91         System.out.println();
 92     }
 93 
 94     // 根据位置查找节点信息
 95     public Node findByPos(int index) {
 96         Node current = first;
 97         while (index != pos++) {
 98             current = current.next;
 99         }
100         return current;
101     }
102 
103     // 根据数据查找节点信息
104     public Node findByData(int data) {
105         Node current = first;
106         while (data != current.data) {
107             if (current.next == null)
108                 break;
109             current = current.next;
110         }
111         return current;
112 
113     }
114 
115 }

链表与顺序表

链表基本算法

插入结点

删除结点

链表代码实现

推荐阅读