题目描述

链表是数据结构中一种最基本的数据结构，它是用链式存储结构实现的线性表。它较顺序表而言在插入和删除时不必移动其后的元素。现在给你一些整数，然后会频繁地插入和删除其中的某些元素，会在其中某些时候让你查找某个元素或者输出当前链表中所有的元素。

下面给你基本的算法描述：

图1：链表类型的定义以及获得链表元素的算法描述

图2：链表的插入算法描述

图3：链表的删除算法描述

图4：链表的创建算法描述

输入格式

输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。

第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。如果是“get”或者“delete”，则其后跟着一个整数a，代表获得或者删除第a个元素；如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e；“show”之后没有整数。

输出格式

如果获取成功，则输出该元素；如果删除成功则输出“delete OK”；如果获取失败或者删除失败，则输出“get fail”以及“delete fail”。如果插入成功则输出“insert OK”，否则输出“insert fail”。如果是“show”则输出列表中的所有元素，如果列表是空的，则输出“Link list is empty”。注：所有的双引号均不输出。

样例输入

3 3 2 1

21

show

delete 1

show

delete 2

show

delete 1

show

delete 2

insert 2 5

show

insert 1 5

show

insert 1 7

show

insert 2 5

show

insert 3 6

show

insert 1 8

show

get 2

样例输出

1 2 3

delete OK

2 3

delete OK

2

delete OK

Link list is empty

delete fail

insert fail

Link list is empty

insert OK

5

insert OK

7 5

insert OK

7 5 5

insert OK

7 5 6 5

insert OK

8 7 5 6 5

7

详细代码

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class LianBiao {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        ArrayList<Integer> list=new ArrayList<>();//初始化定义数组队列list
        Stack<Integer> stack=new Stack<>();//初始化栈stack
        //向栈内赋值
        for (int i = 0; i < n; i++) {
            int a=sc.nextInt();
            stack.add(a);
        }
        //取出栈内元素赋给list
        for (int i = 0; i < n; i++) {
            list.add(stack.pop());
        }

        int m=sc.nextInt();
        for (int i = 0; i < m; i++) {
            String s=sc.next();
            switch (s){
                case"get":
                    int a1=sc.nextInt();
                    //判断位置是否超出范围
                    if(a1>list.size()||a1<1){
                        System.out.println("get fail");
                    }else {
                        System.out.println(list.get(a1-1)/*添加元素*/);
                    }
                    break;
                case"insert":
                    int a2=sc.nextInt();
                    int e=sc.nextInt();
                    //判断位置是否超出范围
                    if(a2>list.size()||a2<1) {
                        //考虑特殊情况【链表为空但选择位置为表头，即list.size（）==0并且a2==1】
                        if (list.size() == 0 && a2 == 1) {
                            list.add(a2 - 1, e);
                            System.out.println("insert OK");
                        } else {
                            System.out.println("insert fail");
                        }
                    }else {
                        list.add(a2 - 1, e);
                        System.out.println("insert OK");
                    }
                    break;

                case"delete":
                    int a3=sc.nextInt();
                    //判断位置是否超出范围
                    if(a3>list.size()||a3<1){
                        System.out.println("delete fail");
                    }else{
                        list.remove(a3-1);//删除元素
                        System.out.println("delete OK");
                    }

                    break;
                case"show":
                    //若链表为空
                    if(list.size()==0){
                        System.out.println("Link list is empty");
                    }else{
                        for(Integer t:list){
                            System.out.print(t+" ");
                        }
                        System.out.println();
                    }
                    break;
            }
        }
    }
}

重点

利用到Arraylist类和Stack类：

ArrayList 是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。

Arraylist详解转载：

http://t.csdn.cn/g4z1Y（作者：迹忆客）

栈(Stack)是 Vector的一个子类，它实现了一个标准的后进先出的栈，也定义了自己的一些方法

Stack详解转载：

http://t.csdn.cn/INsGE（作者：计算机菩萨）

http://t.csdn.cn/YKlvA（作者：煮酒话桑麻）