ArrayListクラスとLinkedListクラスの実装

34904 ワード

ArrayListクラスとLinkedListクラスの実装

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class MyList {
    public static void main(String[] args) {
        test1();// 
        test2();// 
    }
// 
    private static void test2() {
        MyLinkedList linkedList = new MyLinkedList();
        List<Integer> list1 = new LinkedList<>();
        linkedList.addFirst(4);
        linkedList.addFirst(3);
        linkedList.addFirst(2);
        linkedList.addFirst(1);
        linkedList.printf();
        linkedList.addLast(5);
        linkedList.addLast(6);
        linkedList.printf();
        linkedList.removeFirst();
        linkedList.printf();
        linkedList.removeLast();
        linkedList.printf();
        System.out.println(linkedList.getSize());
        System.out.println(linkedList.isEmpty());
    }
// 
    private static void test1() {
        MyArrayList arrayList = new MyArrayList();
        List<Integer> list = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.printfList();
        arrayList.removeElement(2);
        arrayList.printfList();
        arrayList.addIndex(0,9);
        arrayList.printfList();
        System.out.println(arrayList.get(0));
        System.out.println(arrayList.isEmpty());
    }
}

// ----------------------------------------------------
class MyArrayList{
    int[] array;
    int size;
    public MyArrayList(){
       this.array = new int[1];
       this.size = 0;
    }
    // 
    public int get(int index) {
        if(index >= size || index < 0) {
            return -1;
        }
        return array[index];
    }
    // 
    public void add(int element){
        if(size >= array.length) {
            array = Arrays.copyOf(array,array.length*2);
        }
        array[size] = element;
        size++;
    }
    public void addIndex(int index, int element) {
        if(index > size || index < 0){
            return;
        }
        if(size >= array.length) {
            Arrays.copyOf(array,array.length*2);
        }
        for(int i = size; i > index; i--) {
            array[i] = array[i - 1];
        }
        array[index] = element;
        size ++;
    }
    // 
    public void removeIndex(int index){
        if(index < 0 || index >= size) {
            return;
        }
        for(int i = index; i < size; i++) {
            array[i] = array[i + 1];
        }
        size --;
    }
    // 
    public void removeElement(int element) {
        for (int i = 0; i < size; i++) {
            if (element == array[i]) {
                removeIndex(i);
            }
        }
    }
    // 
    public void printfList() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    // 
    public boolean isEmpty() {
        return size == 0;
    }
}
// -------------------------------------------------
class Node{
    int val;
    Node next;
    public Node(int val,Node next){
        this.next = next;
        this.val = val;
    }
    public Node (int val) {
       this(val,null);
    }
    @Override
    public String toString() {
        return this.val + " ";
    }
}
class MyLinkedList{

    int size;
    Node head;
    public MyLinkedList(){
        size = 0;
        head = new Node(0);
    }
    // 
    public void addFirst(int element){
        Node node = new Node(element);
        if (head.next == null) {
            head.next = node;
            size ++;
            return;
        }
        node.next = head.next;
        head.next = node;
        size++;
    }
    // 
    public void addLast(int element) {
        Node node = new Node(element);
        Node cur = head.next;
        for(int i = 1; i < size; i++){
            cur = cur.next;
        }
        cur.next = node;
        size ++;
    }
    // 
    public void removeFirst() {
        if(head.next == null) {
            return;
        }
        size --;
        head.next = head.next.next;
    }
    // 
    public void removeLast() {
        if(head.next == null) {
            return;
        }
        Node cur = head;
        for(int i = 1; i < size; i++){
            cur = cur.next;
        }
        cur.next = null;
        size--;
    }
    // 
    public int getSize(){
        return size;
    }
    // 
    public boolean isEmpty() {
        return size == 0;
    }
    // 
    public void printf() {
        Node cur = head.next;
        if(cur == null) {
            System.out.println(" ");
            return;
        }
        while(cur != null){
            System.out.print(cur);
            cur = cur.next;
        }
        System.out.println();
    }

}