数据结构（2）线性结构

特征：

• 1．集合中必存在唯一的一个"第一个元素"；
• 2．集合中必存在唯一的一个"最后的元素"；
• 3．除最后元素之外，其它数据元素均有唯一的"后继"；
• 4．除第一元素之外，其它数据元素均有唯一的"前驱"。

简而言之，就是有头有尾，中间相连的一条线（不能使一个连多个，一个元素头和尾只能分别连一个）

线性表是线性结构的抽象的表现形式

线性表有常见的两种实现方式

• 1.顺序表
  上一节所说的存储结构的顺序存储结构实现的线性表
• 2.链式表
  上一节所说的存储结构的链式存储结构实现的线性表

1.数组（array）

数组是指有序的元素序列
以java中的数组为例（int[3]）,原理就是读取到显式声明的[3]，就在内存中开辟出一块连续的空间（分成三份），然后将每个元素赋一个默认值。
所以数组是顺序表。
如图所示：

2.栈（stack）

栈是一种特殊的线性表，他的特点是先进后出，插入和删除只能在数据的一端进行。
以java中的stack为例，stack 继承自 Vector（动态长度的数组），通过pop方法移除顶端的数据，通过push来向顶端插入数据
如图所示：从上边进，从上边出

pop方法

public synchronized E pop() {
        E       obj;
        int     len = size();
        //返回堆栈顶部的对象，（通过获取倒数第一个对象实现）
        obj = peek();
        //移除最上边的元素（长度-1），
        removeElementAt(len - 1);
        return obj;
    }

//Vector中的方法
public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
        	//将截取后的列表替换原来列表
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }

push方法

    public E push(E item) {
    	//将元素添加到最末尾
        addElement(item);
        return item;
    }


//Vector中的方法
    public synchronized void addElement(E obj) {
        modCount++;
         //增加数组长度
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

3.队列（Queue）

队列也是一种特殊的线性表，他的特点是后进后出，在一端插入（队尾），另一端删除（对头）。
以java中的 LinkedList（实现了Deque，Deque又实现了Queue（Queue为接口））为例
如图所示：一头进，另一头出

add方法

   public boolean add(E e) {
   		//末尾添加新元素
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last;
        //由于是链表实现，所以为节点，l为e链接的前一个元素，e为新元素，第三个null是链接右边的
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

remove方法

   public E remove() {
        return removeFirst();
    }
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
	//移除第一个，并且把第二个当成第一个
    private E unlinkFirst(Node<E> f) {
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

3.双向链表（Double Linked List）

链表是一种存储结构为链式存储结构的线性表
双向则为节点存贮前和后两个链接，单项则为前或者后一个节点
如图所示：

以下是java的LinkedList基本结构，增删改查都以此进行

//一个链表的基本结构，开始结尾和长度
public class LinkedList<E>{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    public LinkedList() {
    }
}
//一个节点的元素，当前节点，前一个节点和后一个节点
 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

4.双向队列（Double-ends Queues）

集合了队列和栈的特点，两端都可以出队，入队

5.字符串（String）

即是多个字符组成的一个数组
java则是一个字符数组（char[]）