java常用数据结构

一：通过一些源码展示各种数据结构的使用方法：
1.顺序表
概念及结构 ：
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组 上完成数据的增删查改

public interface ISequence
{    //在pos位置插入val  
boolean add(int pos,Object data);   
//查找关键字key 找到返回key的下标，没有返回null;   
int search(Object key);  
//查找是否包含关键字key是否在顺序表当中(这个和search有点冲突)  
boolean contains(Object key);  
//得到pos位置的值   
Object getPos(int pos); 
//删除第一次出现的关键字key   
Object remove(Object key);  
//得到顺序表的长度    
int size();   
//打印顺序表 
void display();  
//清空顺序表以防内存泄漏   
void clear();
}

2.链表
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的引用链 接次序实现的 。

链表的种类:

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。
   1. 带头循环单链表：结构较无头单向非循环链表简单。
   2. 不带头双向循环链表：在Java的集合框架库中LinkedList底层实现就是不带头双向循环链表

// 1、无头单向非循环链表实现
public interface ILinked
{    //头插法 
void addFirst(int data);   
//尾插法   
void addLast(int data);   
//任意位置插入,第一个数据节点为0号下标 
boolean addindex(int index,int data);   
//查找是否包含关键字key是否在单链表当中 
boolean contains(int key);
//删除第一次出现关键字为key的节点
    int remove(int key);  
        //删除所有值为key的节点 
        void removeAllKey(int key);  
        //得到单链表的长度    
        int getLength();  
        void display();    
        void clear(); 
        }
//2、带头循环单链表实现
public interface ICLinked
{    //头插法   
void addFirst(int data);  
//尾插法   
void addLast(int data); 
//任意位置插入,第一个数据节点为0号下标  
boolean addindex(int index,int data);   
//查找是否包含关键字key是否在单链表当中   
boolean contains(int key);   
//删除第一次出现关键字为key的节点   
int remove(int key);    
//删除所有值为key的节点  
void removeAllKey(int key); 
//得到单链表的长度  
int getLength(); 
void display();   
void clear();
}
/ 3、不带头双向链表实现
public interface IDoubleLinked 
{    //头插法  
void addFirst(int data);   
//尾插法   
void addLast(int data);
//任意位置插入,第一个数据节点为0号下标   
boolean addindex(int index,int data);  
//查找是否包含关键字key是否在单链表当中  
boolean contains(int key);   
//删除第一次出现关键字为key的节点  
int remove(int key);   
//删除所有值为key的节点   
void removeAllKey(int key); 
//得到单链表的长度   
int getLength();  
void display();   
void clear(); 
}

3.栈
栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小

interface MyStack
{    // 判断这个栈是否为空栈 
boolean empty();        
// 返回栈顶元素，但不出栈  
int peek();    
// 返回栈顶元素，并且出栈    
int pop();        
// 将 item 压入栈中 
void push(int item);   
// 返回元素个数    
int size(); 
}

4.队列
队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。

interface IMyQueue
{    // 判断这个队列是否为空  
boolean empty();    
// 返回队首元素，但不出队列  
int peek();    
// 返回队首元素，并且出队列  
int poll();  
// 将 item 放入队列中 
void add(int item);    
// 返回元素个数  
int size(); 
}

5：二叉树
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树 的二叉树组成。
1）二叉树的特点：

1. 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
   1. 二叉树的子树有左右之分，其子树的次序不能颠倒

2）特殊的二叉树：

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
2. 1. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

3）二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构
1.二叉树顺序存储在 物理上是一个数组，在逻辑上是一颗二叉树。

1. 链式存储： 二叉树的链式存储结构是指，用链表来表示一棵二叉树，即
   用链来指示元素的逻辑关系。 通常的方法是链表 中每个结点由三个域组成，
   数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在
   的链结 点的存储地址 。

   class Node {  
   int value;    // 结点中的数据域    
   Node leftChild;    // 保存左孩子结点 
   Node rightChild;   // 保存右孩子结点
   }

   （1）二叉树的顺序存储结构：一般是一颗完全二叉树。
   引入堆的概念：（利用数组的存储结构，存放一颗完全二叉树）
   堆的概念及结构
   如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
   堆的性质：
   堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树。

（2）二叉树的链式存储结构。

// 结点个数
int getSize(Node root);

// 叶子结点个数
int getLeafSize(Node root);

// 第 k 层结点个数
int getKLevelSize(Node root, int k);

// 查找，依次在二叉树的 根、左子树、右子树 中查找 value，如果找到，
返回结点，否则返 null
Node find(Node root, int value);