动态数组、栈、队列底层依托静态数组；靠resize解决固定容量问题
链表：真正的动态数据结构
优点：真正的动态，不需要处理固定容量的问题。
缺点：丧失了随机访问的能力
数组最好用于索引有语意的情况 score[2]
最大的优点：支持快速查询
链表不适合用于索引有语意的情况
最大的优点：动态
public class LinkedList <E>{
private class Node{
public E e;
public Node next;
public Node(E e,Node next){
this.e=e;
this.next=next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
@Override
public String toString(){
return e.toString();
}
}
private Node dummyHead;
int size;
public LinkedList(){
dummyHead=new Node(null,null);
size=0;
}
//获取链表中元素的个数
public int getSize(){
return size;
}
//返回链表是否为空
public boolean isEmpty(){
return size==0;
}
//在链表的index(0-based)添加新的元素e
public void add(int index,E e){
if(index<0||index>size)
throw new IllegalArgumentException("Add failed.Illegal index.");
Node prev=dummyHead;
for(int i=0;i<index;i++)
prev=prev.next;
prev.next=new Node(e,prev.next);
size++;
}
//在链表头添加新的元素e
public void addFirst(E e){
add(0, e);
}
//在链表末尾添加新的元素e
private void addLast(E e) {
add(size,e);
}
//获得链表的第index个位置的元素
public E get(int index){
if(index<0||index>=size)
throw new IllegalArgumentException("Get failed.Illegal index.");
Node cur=dummyHead.next;
for(int i=0; i<index;i++)
cur=cur.next;
return cur.e;
}
//获取链表的第一个元素
public E getFirst(){
return get(0);
}
//获取链表的最后一个元素
public E getLast(){
return get(size-1);
}
//修改链表的第index个位置的元素为e
public void set(int index,E e){
if(index<0||index>=size)
throw new IllegalArgumentException("Get failed.Illegal index.");
Node cur=dummyHead.next;
for(int i=0;i<index;i++)
cur=cur.next;
cur.e=e;
}
//查找链表中是否e
public boolean contains(E e){
Node cur=dummyHead.next;
while(cur !=null){
if(cur.e.equals(e))
return true;
cur=cur.next;
}
return false;
}
//从链表中删除index位置的元素，返回删除的元素
public E remove(int index){
if(index<0||index>=size)
throw new IllegalArgumentException("Get failed.Illegal index.");
//找到要删除的前一个节点
Node prev=dummyHead;
for(int i=0;i<index;i++)
prev=prev.next;
Node retNode=prev.next;
prev.next=retNode.next;
retNode.next=null;
size--;
return retNode.e;
}
//从链表中删除第一个元素，返回删除的元素
public E removeFirst(){
return remove(0);
}
//从链表中删除最后一个元素，返回删除的元素
public E removeLast(){
return remove(size-1);
}
@Override
public String toString(){
StringBuilder res=new StringBuilder();
//与下面的写法等价
// Node cur=dummyHead.next;
// while(cur!=null){
// res.append(cur+"->");
// cur=cur.next;
// }
for(Node cur=dummyHead.next;cur!=null;cur=cur.next)
res.append(cur+"->");
res.append("NULL");
return res.toString();
}
}
public class Main {
public static void main(String[] args){
LinkedList<Integer> linkedList=new LinkedList<>();
for(int i=0;i<5;i++){
linkedList.addFirst(i);
System.out.println(linkedList);
}
linkedList.add(2, 666);
System.out.println(linkedList);
linkedList.remove(2);
System.out.println(linkedList);
linkedList.removeFirst();
System.out.println(linkedList);
linkedList.removeLast();
System.out.println(linkedList);
}
}
使用链表实现栈：
public class LinkedListStack<E> implements Stack<E>{
private LinkedList<E> list;
public LinkedListStack() {
list=new LinkedList<>();
}
@Override
public int getSize(){
return list.getSize();
}
@Override
public boolean isEmpty(){
return list.isEmpty();
}
@Override
public void push(E e){
list.addFirst(e);
}
@Override
public E pop(){
return list.removeFirst();
}
@Override
public E peek(){
return list.getFirst();
}
@Override
public String toString(){
StringBuilder res=new StringBuilder();
res.append("Stack:top");
res.append(list);
return res.toString();
}
public static void main(String[] args){
LinkedListStack<Integer> stack=new LinkedListStack<>();
for (int i=0;i<5;i++){
stack.push(i);
System.out.println(stack);
}
stack.pop();
System.out.println(stack);
}
}
测试：
private static double testStack(Stack<Integer> stack,int opCount){
long startTime=System.nanoTime();
Random random=new Random();
for(int i=0;i<opCount;i++)
stack.push(random.nextInt(Integer.MAX_VALUE));
for(int i=0;i<opCount;i++)
stack.pop();
long endTime=System.nanoTime();
return (endTime-startTime)/1000000000.0;
}
public static void main(String[] args){
int opCount=100000;
ArrayStack<Integer> arrayStack=new ArrayStack<>();
double time1=testStack(arrayStack, opCount);
System.out.println("arrayStack,time: "+time1+" s");
LinkedListStack<Integer> linkedListStack=new LinkedListStack<>();
double time2=testStack(linkedListStack, opCount);
System.out.println("linkedListStack,time: "+time2+" s");
}
使用链表实现队列：
public class LinkedListQueue<E> implements Queue<E> {
private class Node{
public E e;
public Node next;
public Node(E e,Node next){
this.e=e;
this.next=next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null,null);
}
@Override
public String toString(){
return e.toString();
}
}
private Node head,tail;
private int size;
public LinkedListQueue(){
head=null;
tail=null;
size=0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size==0;
}
@Override
public void enqueue(E e){
if(tail==null){
tail=new Node(e);
head=tail;
}else{
tail.next=new Node(e);
tail=tail.next;
}
size++;
}
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
Node retNode=head;
head=head.next;
retNode.next=null;
if(head==null)
tail=null;
size--;
return retNode.e;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return head.e;
}
@Override
public String toString(){
StringBuilder res= new StringBuilder();
res.append("Queue:front");
Node cur=head;
while (cur!=null) {
res.append(cur+"->");
cur=cur.next;
}
res.append("NULL tail");
return res.toString();
}
public static void main(String[] args) {
LinkedListQueue<Integer> queue=new LinkedListQueue<>();
for(int i=0; i<10;i++){
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
public static void main(String[] args){
int opCount=10000;
ArrayQueue<Integer> arrayStack=new ArrayQueue<>();
double time1=testQueue(arrayStack, opCount);
System.out.println("arrayStack,time: "+time1+" s");
LoopQueue<Integer> loopQueue=new LoopQueue<>();
double time2=testQueue(loopQueue, opCount);
System.out.println("loopQueue,time: "+time2+" s");
LinkedListQueue<Integer> linkedListQueue=new LinkedListQueue<>();
double time3=testQueue(linkedListQueue,opCount);
System.out.println("linkedListQueue,time:"+time3+" s");
}
