알고리즘-자료구조-리스트 구현

자료구조 구현(자바)

• ArrayList

public class ArrayList {
    private int[] data;
    private int size;

    public ArrayList(){
        data = new int[10];
        size = 0;
    }

    private void resize(){
        int[] newData = new int[data.length * 2];
        for(int i = 0; i < data.length; i++){
            newData[i] = data[i];
        }
        data = newData;
    }
    
    public void add(int value){
        if(size == data.length){
            resize();
        }
        data[size] = value;
        size++;
    }

    public int get(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        return data[index];
    }

    public int size(){
        return size;
    }
}

• LinkedList

public class LinkedList {
    private Node head;
    private int size;

    public LinkedList(){
        head = null;
        size = 0;
    }

    public void add(int value){
        Node newNode = new Node(value);

        if(head == null){
            head = newNode; // head가 없을 경우 새로 생성한 노드를 head로
        }
        else{
            Node currentNode = head;
            //head가 있을 경우 next가 null일 때까지 이동
            while(currentNode.next != null){
                currentNode = currentNode.next;
            }
            currentNode.next = newNode;
        }
        size++;
    }

    public int get(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }

        Node currentNode = head;
        for(int i = 0; i < index; i++){
            currentNode = currentNode.next;
        }

        return currentNode.value;
    }

    public int size(){
        return size;
    }
}

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