一 前言
数据结构的概念很多，我的理解：1.规定了数据的物理结构（怎么存的 连续 （数组）非连续（链表）） 2.数据的逻辑结构（栈，队列，树） 3.增删改查等一系列基本操作 （队列的出队列操作等）
所有就有很多概念，链表（物理结构上非连续存储的），栈，队列（特殊的逻辑结构，增删算法复杂度达到O（1））:具体的实现有不同的物理结构，也就是数组和链表两种方式。
二 链表的java简单实现
有一次面试，面试官让我自己定义一个双向链表，由于之前没写过。写的很乱，最近复习自己写了一个简单实现 ，核心就是定义一个类，而链表的结构定义为内部类，这样符合java面向对象的思路。
public class MyList {
class Node{
Node next;
int val;
Node(){
}
Node(int n){
val =n;
}
} //定义一个节点结构，包括下一个节点的引用，和本节点的数据
private Node head;
private Node last;
private int size; //实际的链表类中保存头结点，尾节点 ，和链表的大小
MyList(){
head = new Node();
last = head;
}
public void add(int val){
Node node = new Node(val);
last.next = node;
last = last.next; //尾插 并移动链表尾节点
size++;
}
public void add(int val, int i) {
if(i>size+1||i<=0)
throw new RuntimeException("插入的位置不合法");
if(i==size+1) {
add(val);
return;
}
Node pre=head;
Node next = head.next;
while(i>1){
pre = pre.next;
next = pre.next;
i--;
}
Node now = new Node(val);
pre.next = now;
now.next = next;
size++;
}
public boolean isEmpty(){
return size == 0;
}
public int get(int i){
if(i<=0||i>size)
throw new RuntimeException("获取的位置不合法");
Node now = head;
while(i>0){
now = now.next;
i--;
}
return now.val;
}
public void delAll(){
size = 0;
head.next = null;
last = head;
}
public int del(int i) {
if (i <= 0 || i > size)
throw new RuntimeException("删除的位置不合法");
int j = i;
Node now = head;
while(i>1){
now = now.next;
i--;
}
Node node = now.next;
now.next = now.next.next;
if(j==size){
last = now;
}
size--;
return node.val;
}
public void showList(){
if(size==0) {
System.out.println("链表为空");
return;
}
Node now = head.next;
while(now!=null){
System.out.print(now.val+" ");
now = now.next;
}
}
}
三 栈 队列的java简单实现
首先栈，队列都是逻辑结构，他们的增加和删除都能达到O（1）的代价，但是增删的位置有规定，也就是队列先插入的先删除，栈的先插入的后删除。链表实现主要考验对节点的操作，我这里选择数组实现，其实就是在内部结构中加一个int保存数组的尾部。由于是简单实现，也没有扩容等操作。
public class MyQueue {
private int arr[]; //队列的数据存储
private int begin; //队首 用于出队列
private int end; //队尾 用于入队列
private int size; //队列的大小
MyQueue(int n){
if(n<=0)
throw new RuntimeException("队列大小设置出错");
arr = new int[n];
begin=end=0;
size=0;
}
MyQueue(){
this(10); //默认队列长度是10
}
//入队列 满了就抛异常
public void offer(int val) {
if(size>=arr.length)
throw new RuntimeException("队列满了");
arr[end] = val;
end = (++end) % arr.length;
size++;
}
public int poll(){
if(isEmpty())
throw new RuntimeException("队列是空的");
int val = arr[begin];
begin = (++begin) % arr.length;
size--;
return val;
}
public boolean isEmpty(){
return size == 0;
}
}
栈：
public class MyStack {
private int arr[];
private int size;
private int top;
MyStack(int n){
if(n<=0)
throw new RuntimeException("栈大小定于错误");
arr = new int[n];
}
MyStack(){
this(10);
}
public void push(int val){
if(size>=arr.length)
throw new RuntimeException("栈满了");
arr[top++] = val;
size++;
}
public int pop(){
if(size==0)
throw new RuntimeException("栈是空的");
top--;
size--;
return arr[top ];
}
public boolean isEmpty() {
return size == 0;
}
}