[Java 기초] 배열과 리스트의 관계

배열과 리스트의 관계

 

ArrayList

ArrayList는 자료구조의 한 종류로서 동적으로 배열의 크기를 변경할 수 있다.

그럼 ArrayList는 어떻게 배열의 크기를 조정하는 것일까?

1. ArrayList의 초기 크기는 10이다.
2. add()로 인해 사이즈가 꽉 찼을 시 현재의 1.5배를 증가시켜 새로운 배열을 생성한다.
3. 1.5배 증가시킨 새로운 배열에 현재의 배열을 copy한다.

만약 배열의 추가 및 삭제가 반복적으로 일어나게 된다면, 기존 배열에 있는 데이터들은 공간을 매꾸기 위해서 이동해야한다. 즉, 성능적인 이슈가 발생할 수 있다는 것이다.
이 때는, ArrayList 보다는 LinkedList로 배열을 생성하는 것이 더 적합할 수 있다.

 

LinkedList

LinkedList는각 인스턴스들이 다음 인스턴스의 주소를 가리키며 연결하는 것으로, 추가 혹은 삭제를 할 경우에는 다음 인스턴스의 주소를 변경만 해주면 된다.

//링크드 리스트 기본 설정
public class MyLinkedList {
    private Node head;
    private Node tail;
    private int size = 0;
    private class Node {
        private Object data;
        private Node next;
        public Node(Object input) {
            this.data = input;
            this.next = null;
        }
    }
    ...
}

 

ArrayList와 LinkedList

• 일반적으로 원소에 랜덤으로 접근할 수 있어야 하거나 리스트 크기가 클수록 ArrayList를 사용하면 좋다.
• 리스트의 첫 부분이나 중간에 원소를 삽입/삭제할 일들이 많다면 LinkedList를 사용하면 좋다.
• ArrayList는 자료검색이 용이하다
  • why? 순서가 보장되어 있고 인덱스로 접근이 가능하기 때문이다.
• 반면, LinkedList는 자료검색하기가 힘들다.
  • why? 다음 객체를 참조하여 연결된 리스트로서 검색하기 위해서는 일일히 다 찾아야한다.

 

Queue

Queue

큐는 흔히 알듯이, FIFO(선입선출) 방식으로 처리하는 자료구조이다.

반대되는 개념으로는 LIFO(후입선출) 방식인 Stack이 있는데 참고 해두면 좋다.

 

Queue의 메소드

• add(); 새 원소를 추가한다 - 꼬리부터 쌓는다.
• remove(); 오래된 원소를 제거한다 - 머리부터 삭제한다.
• peek(); 오래된 원소를 반환하지만 제거하지는 않는다. - 머리부터 확인한다.

 

Priority Queue

우선순위 큐라고 칭하며, Queue와는 다르게 데이터를 꺼낼 때 우선순위가 가장 높은 데이터가 먼저 나오는 방식이다.

단, 제네릭 타입이 사용자가 정의한 객체일 경우 Comparable의 compareTo()를 구현을 통해 우선순위를 정해줘야 올바른 Priority Queue를 실행할 수 있다.

why? 우선순위 큐의 offer는 큐 한쪽 끝에 차곡차곡 저장하는데, 이 때 추가되는 객체를 Comparable 인터페이스로 Up Casting을 진행하여 우선순위를 정한다. 그러므로 Comparable를 implement하지 않아 구현되어 있지 않으면 ClassCastException이 발생하게 된다.

public class Student implements Comparable<Student>{
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Student target) {
        return this.age <= target.age ? 1 : -1;    //내림차순
    }

    public String toString() {
        return "이름 : " + name + ", 나이 :" + age;
    }
}

public class PQMain {
    public static PriorityQueue<Student> getPriorityQueueOfStudents() {
        PriorityQueue<Student> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(new Student("A", 30));
        priorityQueue.offer(new Student("B", 30));
        priorityQueue.offer(new Student("C", 29));
        priorityQueue.offer(new Student("D", 31));
        priorityQueue.offer(new Student("E", 27));

        return priorityQueue;
    }

    public static void main(String [] args) {
        PriorityQueue<Student> priorityQueue = getPriorityQueueOfStudents();

        while(!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}

//결과
이름 : D, 나이 :31
이름 : A, 나이 :30
이름 : B, 나이 :30
이름 : C, 나이 :29
이름 : D, 나이 :27

 

offer 메소드를 자세히 살펴보자

//offer
public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
}

//siftup
private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
}

//siftUpComparable
private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;    //Comparable로 upCasting 진행
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)	//사용자가 구현한 CompareTo로 우선순위 정함 
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
}

 

Deque

Double-ended Queue의 약자로서, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.

Queue와 Stack을 합친 형태로 생각할 수 있다.