数据结构基础

线性表

线性表是按顺序存储数据时常用的一种数据结构。
实现线性表的方式有两种：

数组 ArrayList

数组是大小固定的，可以在数组不能存储新元素时创建一个更大的数组来替换当前数组。

add

public void add(int index,E e){

  if(size>=data.length){
  E[] newData=(E[])(new Object[size*2+1]);
  System.arraycopy(data,0,newData,0,size);
  data=newData;
  }
 } 
  for (int i=size-1;i>=index;i--)
   data[i+1]=data[i];
  
  data[index]=e;
  size++;
 }

链式结构

LinkedList 链表由链接在一起的多个结点组成,每个结点都包含元素和一个名为next的数据域，next指向下一个元素，如果结点是链表中的最后一个，next所包含的值为null。变量head指向链表的第一个结点，tail指向最后一个结点。

class Node<E>{
  E element;
  Node<E> next;
  
  public Node(E e){
  element=e;

 }

addFirst

public void addFirst(E e){

Node<E> newNode=new Node<E>(e);
newNode.next=head;//插入结点到起始位置
head=newNode;//head指向新结点
size++;

if(tail==null)
 tail=head;
}

addLast

public void addLast(E e){
Node<E> newNode=new Node<E>(e);

if(tail==null){
  head=tail=newNode;
}
else{
  tail.next=newNode;//链接该结点与最后一个结点
  tail=tail.next;//tail指向新结点
}

size++;
}

add,将新结点赋给current.next，并将temp赋给新结点的next

public void add(int index,E e){

if(index==0) addFirst(e);
else if(index>=size) addLast(e);
else{
  Node<E> current=head;
  for(int i=1;i<index;i++)
    current=current.next;
  Node<E> temp=current.next;
  current.next=new Node<E>(e);
  (current.next).next=temp;
  size++;
  }
 }

循环单链表，链表中最后一个结点的指针指回第一个结点。
双向链表，包含带两个指针的结点，一个指针指向下一个结点，另一个指向前一个结点。可以从前开始遍历，也可以从后开始遍历。

栈和队列

栈

栈是限定仅在栈顶进行插入或删除的线性表，栈为后进先出线性表。

队列

队列是一种先进先出的线性表，只允许 一端插入，一端删除