复习系列1-DS单链表--类实现

DS单链表--类实现

题目描述与顺序表一样；一开始贪图方便用 List 直接A过，很轻松，想了想还是自己手动实现一遍，以对原理更加了解。代码写得一般，head指针为了方便还是存了数据，但是show 的时候不读取。【当然期末考试要是遇到要用链表，还是用List，方便快捷】

题目描述

用C++语言和类实现单链表，含头结点

属性包括：data数据域、next指针域

操作包括：插入、删除、查找

注意：单链表不是数组，所以位置从1开始对应首结点，头结点不放数据

输入

n

第1行先输入n表示有n个数据，接着输入n个数据
第2行输入要插入的位置和新数据
第3行输入要插入的位置和新数据
第4行输入要删除的位置
第5行输入要删除的位置
第6行输入要查找的位置
第7行输入要查找的位置

输出

n

数据之间用空格隔开，

第1行输出创建后的单链表的数据

每成功执行一次操作（插入或删除），输出执行后的单链表数据

每成功执行一次查找，输出查找到的数据

如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出单链表

样例输入

6 11 22 33 44 55 66 3 777 1 888 1 11 0 5

样例输出

11 22 33 44 55 66 11 22 777 33 44 55 66 888 11 22 777 33 44 55 66 11 22 777 33 44 55 66 error error 44

Solution：

import java.util.*;
/**
 * @author: Liu Canbin
 * @date: 2019/1/2
 */

public class Main {
//    private static List<Integer> list = new ArrayList<Integer>();
    private static List list = new List();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // init data
        int n = scanner.nextInt();
        for (int i = 0; i <n ; i++) {
            list.add(scanner.nextInt());
        }
        show();
        //insert
        for (int i = 0; i <2 ; i++) {
            int index = scanner.nextInt();
            int data = scanner.nextInt();
            if (index<1 || index>list.size()){
                System.out.println("error");
            }else {
                index--;
                list.add(index,data);
                show();
            }

        }
        //delete
        for (int i = 0; i <2 ; i++) {
            int index = scanner.nextInt();
            if (index<1 || index>list.size()-1){
                System.out.println("error");
            }else {
                index--;
                list.remove(index);
                show();
            }

        }
        //find
        for (int i = 0; i <2 ; i++) {
            int index = scanner.nextInt();
            if (index<1 || index>list.size()-1){
                System.out.println("error");
                continue;
            }
            System.out.println(list.get(index));
        }
    }

    private static void show(){
        for (int i = 1; i <list.size() ; i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
    }
}

class List{
    Node head;

    List(){
        head = new Node(0);
    }
    void add(int data){
        Node node = new Node(data);
        Node temp = head;
        while (temp.next!=null){
            temp = temp.next;
        }
        temp.next =node;
    }
    void add(int index,int data){
        Node node = new Node(data);
        Node temp = head;
        for (int i = 0; i <index ; i++) {
            temp = temp.next;
        }
        node.next =temp.next;
        temp.next = node;

    }
    void remove(int index){
        Node temp = head;
        for (int i = 1; i <index ; i++) {
            temp = temp.next;
        }
        temp.next = temp.next.next;
    }
    int get(int index){
        Node temp = head;
        for (int i = 1; i <index ; i++) {
            temp = temp.next;
        }
        return temp.next.data;
    }

    int size(){
        int sum =0;
        Node temp = head;
        while (temp!=null){
            sum++;
            temp = temp.next;
        }
        return sum;
    }
}

class Node{
    int data;
    Node next;
    public Node(int data){
        this.data =data;
        next = null;
    }
}