2017-11-23发表数据结构和算法

数据结构（二）数组和链表

背包、队列和栈是三种简单的数据类型。那么我们如何去组织上述的数据类型呢？这时候就要用到数组和链表了。

一、数组

数组，简单来说就是将所有的数据排成一排存放在系统分配的一个内存块上，通过使用特定元素的索引作为数组的下标，可以在常数时间内访问数组元素的这么一个结构。

数组的优点

简单、易用
访问元素快（常数时间）

数组的缺点

大小固定：数组在使用前必须先制定固定的大小，可能会造成浪费或者不够用溢出
连续空间块：数组初始分配空间时，有时候无法分配能存储整个数组的内存空间（当数组规模太大时）
插入操作实现复杂：往一个大数组中间插入数据，插入索引后面的数据都要相应地往后移动，这会造成很大的开销

二、链表

链表是一种递归的数据结构。它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型元素和一个指向另一条链表的引用。对于链表来说，初始时仅需要分配一个元素的存储空间。添加新的元素也很容易，不需要做任何内存复制和重新分配的操作。

链表的优点

动态，大小不固定
离散，在内存空间里存储不必连续

链表的缺点

没有随机访问的能力，访问一个元素必须先访问它的上一个元素
链表中的额外指针引用需要浪费内存

链表操作

1. 定义结点

private class Node{
  Item item;
  Node next;
}

2. 访问链表

如果有一个链表的对象实例 first，那么我们可以用 first.item 和 first.next 访问它的实例变量。

3. 构造链表

//创建三个链表对象实例
Node first = new Node();
Node second = new Node();
Node third = new Node();

//每个实例的值
first.item = "to";
second.item = "be";
third.item = "or";

//指向下一个实例
first.next = second;
second.next = third;

我们先 new 了三个链表对象实例，然后给他们的Item赋值，并让他们的next指向下一个链表的引用。（链表是递归的数据结构）

在这里，third.next是null，也就是third.next指向了一个空链表。

链表表示的是一列元素。

4. 在表头插入结点

//步骤一：保存原来的表头
Node oldfirst = first;

//步骤二：创建新的首结点
first = new Node();

//步骤三：设置新结点的实例变量
first.item = "not";
first.next = oldfirst;

5. 删除头结点

1	first = first.next;

6. 在表尾插入结点

//步骤一：保存指向尾结点的链接
Node oldlast = last;

//步骤二：创建新的尾结点
last = new Node();
last.item = "not";

//步骤三：将尾链接指向新结点
oldlast.next = last;

7. 遍历链表

遍历链表的固定模式：

1
2
3

for (Node i = first; i != null; i = i.next){

}

#数据结构和算法