생활코딩) [Java] ArrayList, LinkedList

채개바라 2024. 2. 12. 14:39

2024. 2. 12. 14:39

ArrayList

소개

ArrayList는 배열을 이용해서 리스트를 구현한 것을 의미한다. 장점은 내부적으로 배열을 이용하기 때문에 인덱스를 이용해서 접근하는 것이 빠르다는 것이다. 하지만 데이터의 추가와 삭제가 느리다.

데이터의 추가

ArrayList는 내부적으로 데이터를 배열에 저장한다. 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면 이후의 데이터들이 한칸씩 뒤로 물러나야 한다.

데이터의 삭제

삭제도 추가와 비슷하다. 빈자리가 생기면 빈자리를 채우기 위해서 순차적으로 한 칸씩 땡겨야 한다.

데이터 가져오기

인덱스를 이용해서 데이터를 가져오고 싶을 때 Array로 구현한 리스트는 매우 빠르다. 메모리상의 주소를 정확하게 참조해서 가져오기 때문이다.

배열을 건물에 비유해보자. 각각의 엘리먼트는 그 엘리먼트에 대한 인덱스를 가지고 있다. 인덱스를 안다는 것은 주소를 알고 있는 것과 같다. 반면에 인덱스를 모르는 것은 주소를 모르고 집을 찾아가는 것과 같기 때문에 시간이 오래 걸린다. 인덱스만 알고 있다면 ArrayList에서 데이터를 가져오는 것은 매우 빠르다.

ArrayList 사용법

생성

ArrayList를 사용하기 위해서는 우선 ArrayList 객체를 만들어야 한다.

ArrayList<Integer> numbers = new ArrayList<>();

ArrayList는 java.util.ArrayList에 포함되어 있기 때문에 import를 해야 한다.

import java.util.ArrayList;

추가

엘리먼트를 추가할 때는 add 메서드를 사용한다. add는 배열에 단순히 더해지는 것이기 때문에 빠르게 동작한다.

numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);

특정 위치에 추가하고 싶다면 메서드 add의 첫 번째 인자로 인덱스를 지정한다.

numbers.add(1, 50);

[코드]

package arraylist;

import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        ArrayList <Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        System.out.println("add(값)");
        System.out.println(numbers);

        numbers.add(1, 50);
        System.out.println("\nadd(인덱스, 값)");
        System.out.println(numbers);
    }
}

삭제

특정 인덱스에 위치하는 엘리먼트를 삭제할 때는 remove를 사용한다.

numbers.remove(2); //index 2에 있는 데이터를 삭제

package arraylist;

import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        ArrayList <Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        System.out.println("add(값)");
        System.out.println(numbers);

        numbers.add(1, 50);
        System.out.println("\nadd(인덱스, 값)");
        System.out.println(numbers);

        numbers.remove(2);
        System.out.println("\nremove(인덱스)");
        System.out.println(numbers);
    }
}

가져오기

엘리먼트를 가져올 때는 get을 사용한다. 이때 내부적으로 배열을 사용하기 때문에 매우 빠르게 엘리먼트를 가져올 수 있다.

numbers.get(2) //index 2에 있는 데이터를 가져온다.

크기(size)

ArrayList의 크기를 알고 싶으면 size 메서드를 이용하면 된다.

[코드]

package arraylist;

import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        ArrayList <Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        System.out.println("add(값)");
        System.out.println(numbers);

        numbers.add(1, 50);
        System.out.println("\nadd(인덱스, 값)");
        System.out.println(numbers);

        numbers.remove(2);
        System.out.println("\nremove(인덱스)");
        System.out.println(numbers);

        System.out.println("---------------");
        System.out.println("numbers.get(2): " + numbers.get(2));
        System.out.println("numbers.size(): " + numbers.size());
    }
}

반복

자바에서는 ArrayList를 탐색하기 위한 방법으로 iterator을 제공한다. 이것은 주로 객체 지향 프로그래밍에서 사용하는 반복기법이다. 우선 Iterator 객체를 만들어야 한다.

Iterator <Integer> it = numbers.iterator();

Iterator 객체는 numbers 객체 내부에 저장된 값을 하나씩 순회하면서 탐색할 수 있도록 돕는 객체다.

Iterator <Integer> it = numbers.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

it.next() 메서드를 호출할 때마다 엘리먼트를 순서대로 리턴한다. 만약 더 이상 순회할 엘리먼트가 없다면 it.hasNext()의 값은 false가 되면서 while문이 종료된다.

순회 과정에서 필요에 따라서는 엘리먼트를 삭제/추가하는 작업을 해야 할 것이다. 그런 경우 아래와 같이 처리할 수 있다.

while(it.hasNext()){
    int value = it.next();
    if(value == 30){
        it.remove();
    }
}

it.remove()는 it.next()를 통해서 반환된 numbers의 엘리먼트를 삭제하는 명령이다.

[코드]

package arraylist;

import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        ArrayList <Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        System.out.println("add(값)");
        System.out.println(numbers);

        numbers.add(1, 50);
        System.out.println("\nadd(인덱스, 값)");
        System.out.println(numbers);

        numbers.remove(2);
        System.out.println("\nremove(인덱스)");
        System.out.println(numbers + "\n");

        Iterator <Integer> it = numbers.iterator();
        while(it.hasNext()){
            int value = it.next();
            if(value == 30){
                it.remove();
            }
        }
        System.out.println("30 삭제 후: " + numbers);
    }
}

반복2(순회하는 다른 방법들)

1. Iterator
2. for-each문
3. for문

package arraylist;

import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        ArrayList <Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);

        //1. Iterator
        Iterator <Integer> it = numbers.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
        System.out.println("-----------------------------");

        //2. for-each문
        for (Integer number : numbers) {
            System.out.println(number);
        }
        System.out.println("-----------------------------");

        //3. for문
        for(int i = 0; i<numbers.size(); i++){
            System.out.println(numbers.get(i));
        }

    }
}

LinkedList

소개

LinkedList는 ArrayList와는 다르게 엘리멘트와 엘리멘트 간의 연결(link)을 이용해서 리스트를 구현하는 것을 의미한다.

연결이 무엇인가 알아보자.

메모리

연결에 대해서 알아보기 앞서 컴퓨터가 동작하는 원리를 간단하게 살펴 보자.

컴퓨터에는 3가지 중요한 부품이 있다. CPU, 메모리(Memory), 스토리지(Storage)이다.

메모리는 속도가 매우 빠르다. 반대로 용량이 작다. 그리고 전기를 끄면 데이터가 사라지는 속성을 가지고 있다. 반면에 스토리지는 속도가 느리다. 하지만 용량이 훨씬 크고 전기를 꺼도 데이터가 남아 있다.

이런 이유로 데이터는 기본적으로 스토리지에 저장된다. 하지만 스토리지는 매우 느리기 때문에 CPU와 함께 일을 하기에는 속도면에서 부족하다. 그래서 어떤 프로그램을 실행하면 그 프로그램과 데이터는 메모리로 옮겨진다. CPU는 메모리에 로드된 데이터를 이용해서 여러가지 일을 하게 된다.

메모리의 구조

ArrayList

첫 번째 회사는 모든 직원이 한곳에 모여있어야 한다는 철학이 있기 때문에 사무실이 모여있다. 배열은 건물을 이런 식으로 사용하는 것과 비슷하다. 만약 회사가 성장해서 사무실이 좁아지면 더 이상 새로운 직원을 뽑을 수 없다. 붙어있는 공간이 없기 때문이다. 만약 더 많은 공간이 필요하다면 더 많은 사람을 수용할 수 있는 공간을 찾아서 전체가 이사해야 한다.

LinkedList

linked list는 한 건물 내에서 한 회사가 임대한 사무실이 서로 떨어져 있다. 덕분에 직원이 늘어도 큰 걱정이 없다. 건물에서 비어있는 곳 아무데나 임대해서 들어가면 된다. 그런데 방문자가 사무실을 찾는 방법이 좀 비효율적이다. 위의 그림에 있는 방문자가 3번째 사무실을 찾아가려면 우선 첫 번째 화살표의 사무실을 찾아가야 한다. 이 사무실의 직원에게 다음 사무실이 어딘지 물어본다. 그럼 알려주는 사무실로 이동 한 후에 다시 물어봐서 그 다음 사무실로 이동한다.

이렇게 물어물어 사무실을 찾아가야 하는 방식이 LinkedList이다. 그래서 LinkedList에서는 몇 번째 엘리먼트를 찾는 것이 느리다.

반면에 ArrayList는 엘리먼트가 같은 곳에 모여있다. 만약에 3번째 자리로 가고 싶다면 한 번에 3번째 방으로 갈 수 있다. 찾고자 하는 사무실이 몇 번째에 있는지 알고 있다면 ArrayList는 매우 빠르다.

연결

배열과는 다르게 LinkedList는 그 위치가 흩어져 있기 때문에 서로 연결되어 있어야 한다. 바로 그런 점에서 연결이라는 이름을 갖게 된 것이다.

ArrayList에서는 엘리먼트라는 이름을 사용했지만 LinkedList와 같이 연결된 엘리먼트들은 노드(node, 마디, 교점의 의미) 혹은 버텍스(vertex, 정점, 꼭지점의 의미)라고 부른다. 이런 용어들은 연결성이 강조된 표현이라고 생각하시면 된다. 여기서도 엘리먼트, 노드, 버텍스를 혼용해서 사용하도록 하겠다.

ArrayList와 LinkedList의 차이

	순차적으로 추가/삭제	중간에 추가/삭제	검색
ArrayList	빠르다	느리다	빠르다
LinkedList	느리다	빠르다	느리다

데이터를 1만건 저장 후 수행시간을 측정해보자.

1. "Hello"를 순차적으로 추가

package arraylist;

import java.util.*;

public class LinkedListTest {
    public static void main(String[] args) {
        List<String> arraylist = new ArrayList<>();
        List<String> linkedlist = new LinkedList<>();
        
        long startTime = System.nanoTime();
        for(int i = 0; i<10000; i++){
            arraylist.add("Hello"); //ArrayList에 "Hello"를 순차적으로 저장
        }
        long endTime = System.nanoTime();
        long gap = endTime - startTime;
        System.out.println("ArrayList에 걸린 시간: " + gap + "ns");
        System.out.println("arraylist.size(): " + arraylist.size());
        System.out.println("*****************************************");

        startTime = System.nanoTime();
        for(int i = 0; i<10000; i++){
            linkedlist.add("Hello"); //LinkedList에 "Hello"를 순차적으로 저장
        }
        endTime = System.nanoTime();
        gap = endTime - startTime;
        System.out.println("LinkedList에 걸린 시간: " + gap + "ns");
        System.out.println("linkedlist.size(): " + linkedlist.size());
    }
}

2. "Hello"를 중간에 추가

package arraylist;

import java.util.*;

public class LinkedListTest {
    public static void main(String[] args) {
        List<String> arraylist = new ArrayList<>();
        List<String> linkedlist = new LinkedList<>();

        long startTime = System.nanoTime();
        for(int i = 0; i<10000; i++){
            arraylist.add(0, "Hello"); //ArrayList의 index 0에 "Hello"를 삽입
        }
        long endTime = System.nanoTime();
        long gap = endTime - startTime;
        System.out.println("ArrayList에 걸린 시간: " + gap + "ns");
        System.out.println("arraylist.size(): " + arraylist.size());
        System.out.println("*****************************************");

        startTime = System.nanoTime();
        for(int i = 0; i<10000; i++){
            linkedlist.add(0,"Hello"); //LinkedList의 index 0에 "Hello"를 삽입
        }
        endTime = System.nanoTime();
        gap = endTime - startTime;
        System.out.println("LinkedList에 걸린 시간: " + gap + "ns");
        System.out.println("linkedlist.size(): " + linkedlist.size());
    }
}

3. 검색

package arraylist;

import java.util.*;

public class LinkedListTest {
    public static void main(String[] args) {
        List<String> arraylist = new ArrayList<>();
        List<String> linkedlist = new LinkedList<>();
        for(int i = 0; i<10000; i++){
            arraylist.add("Hello");
        }
        for(int i = 0; i<10000; i++){
            linkedlist.add("Hello");
        }

        //검색
        long startTime = System.nanoTime();
        for(int i = 0; i<10000; i++){
            arraylist.get(i);
        }
        long endTime = System.nanoTime();
        long gap = endTime - startTime;
        System.out.println("ArrayList에 걸린 시간: " + gap + "ns");
        System.out.println("arraylist.size(): " + arraylist.size());
        System.out.println("*****************************************");

        startTime = System.nanoTime();
        for(int i = 0; i<10000; i++){
            linkedlist.get(i);
        }
        endTime = System.nanoTime();
        gap = endTime - startTime;
        System.out.println("LinkedList에 걸린 시간: " + gap + "ns");
        System.out.println("linkedlist.size(): " + linkedlist.size());
    }
}

저작자표시 비영리 변경금지

StartCode