[새싹x코딩온] 웹 개발자 부트캠프 과정 21주차 회고 | Java의 ArrayList와 LinkedList 비교

1. 들어가며

• Java 의 List 중 ArrayList 와 LinkedList 비교해보기

2. List

자바에서 컬렉션 프레임워크가 제공하는 인터페이스 중 List 라는 것이 있다.

List는 순서가 없는 데이터의 집합을 다룰 때 사용하며, 데이터 중복을 허용한다. (Set은 중복 허용 X) 

이번 포스팅에서는 List 에서도 ArrayList 와 LinkedList 를 비교해보고자 한다.

 

배열과 연결리스트 비교

ArrayList 와 LinkedList 를 비교하기 전에 먼저,

ArrayList 와 LinkedList 의 기반이 되는 자료구조인 배열과 연결리스트(링크드리스트)에 대해 먼저 알아보고자 한다.

 

배열

배열은 데이터를 한 열로 연속해서 정렬하는 데이터 구조다.

배열의 데이터는 메모리의 연속된 영역에 순차적으로 저장된다. 

순차적으로 존재하는 배열

 

특정 데이터에 접근할 때, 인덱스를 통해 직접 접근하기 때문에 빠르다.(이를 랜덤 접근이라고 한다.)

예를 들어 a라는 배열이 있다고 했을 때 a[2] 라고 지정하기만 하면 직접 해당하는 인덱스의 데이터에 접근할 수 있다.

 

중간에 요소를 삽입하거나 삭제할 때는 시간이 오래 걸린다.

추가를 할 때는 그 데이터의 추가를 위해 메모리 상 공간을 확보해야 한다. 

만약 n번째 인덱스에 추가를 한다고 하면 그 뒤의 데이터들은 하나씩 뒤로 옮겨진다.

위 다이어그램에서 볼 수 있듯이 새로운 요소 추가를 위해 그 뒤의 모든 요소들을 한 칸씩 뒤로 이동시켜야 한다.

 

 

삭제도 마찬가지로 삭제후에 그 뒤의 데이터들이 하나씩 앞으로 옮겨진다.

 

연결리스트

연결리스트는 데이터를 일직선으로 줄줄이 정렬한 데이터 구조다.

연결리스트의 각 데이터는 포인터를 가지고 있어서 다음 데이터의 메모리 주소를 가리킨다.

연결리스트의 데이터는 배열과 달리 메모리 상에서 연속해서 존재할 필요가 없다.

양방향 연결리스트 데이터 구조

연속적으로 배치되어 있지 않고 개별적으로 저장되어 있어서 특정 데이터에 접근하려면 데이터의 포인터를 따라 찾아간다.(이를 순차 접근 혹은 시퀀셜 액세스 라고 한다.)

즉, 데이터의 개수가 n개라고 가정했을 때 특정 데이터에 접근하고자 하면 맨 처음부터 하나씩 접근해야 하므로 접근시간이 오래걸린다.

 

반면, 데이터의 추가나 삭제가 되면 포인터가 가리키는 주소만 바꿔주면 되기 때문에 추가나 삭제는 쉽다.

위 다이어그램은 20과 30 사이에 25를 추가하는 과정이다. 새로운 노드를 생성하고, 포인터를 조정하면 된다.

추가 전에는 20의 포인터에 30의 주소가 있었다면, 25라는 노드를 생성의 20의 포인터에 25의 주소로 바꿔주는 것이다.

위 다이어그램은 20을 삭제하는 과정이다. 

10의 포인터에서 20을 가리키는 포인터를 30으로 변경하고, 20 노드를 메모리에서 삭제한다.

배열과 달리 연결리스트에서의 추가나 삭제는 요소들을 이동시킬 필요가 없기 때문에 처리 시간이 더 빠르다.

 

둘의 차이점을 표로 나타낸다면 아래와 같다.

 

ArrayList

ArrayList 는 이름에서도 알 수 있듯이, 배열 기반으로 만들어진 List다.

따라서 배열의 특징을 가지고 있다.

자바에서의 배열과 다른점은

자바의 배열은 크기가 고정되어 있지만, ArrayList 는 동적 할당이 가능해서 크기를 미리 지정하지 않아도 된다.

배열 기반이므로 인덱스를 사용한 요소 접근이 빠르지만, 중간에 요소를 삽입하거나 삭제하는 연산은 느리다.

 

LinkedList

List와 Deque 인터페이스의 양방향 연결 리스트를 구현한다.

연결리스트 기반이므로 중간에 요소를 삽입하거나 삭제하는 연산은 빠르지만, 인덱스를 사용한 접근은 느리다.

 

ArrayList vs. LinkedList

반복문을 사용해서 둘의 연산속도를 비교할 것이다.

// ArrayList vs LinkedList
public class CompareList {
    public static void main(String[] args) {
        // ArrayList 컬렉션 객체 생성
        List<String> list1 = new ArrayList<>();

        // LinkedList 컬렉션 객체 생성
        List<String> list2 = new LinkedList<>();

        // 시작, 끝 변수 선언
        long startTime;
        long endTime;

        // ArrauList 의 0번 인덱스에 데이터 추가 (10000회 반복)
        startTime = System.nanoTime(); // 시작시간
        for(int i = 0; i < 10000; i++){
            list1.add(0, String.valueOf(i));
        }
        endTime = System.nanoTime(); // 끝시간

        System.out.println("ArrayList 소요 시간 " + (endTime - startTime));


        // LinkedList 의 0번 인덱스에 데이터 추가 (10000회 반복)
        startTime = System.nanoTime(); // 시작시간
        for(int i = 0; i < 10000; i++){
            list2.add(0, String.valueOf(i));
        }
        endTime = System.nanoTime(); // 끝시간

        System.out.println("LinkedList 소요 시간 " + (endTime - startTime));

        // ArrauList 의 특정인덱스에 접근
        startTime = System.nanoTime(); // 시작시간
        for(int i = 0; i < 10000; i++){
            list1.get(40);
        }
        endTime = System.nanoTime();
        System.out.println("ArrayList 소요 시간 " + (endTime - startTime));


        // LinkedList 의 특정 인덱스에 접근
        startTime = System.nanoTime(); // 시작시간
        for(int i = 0; i < 10000; i++){
            list2.get(40);
        }
        endTime = System.nanoTime(); // 끝시간

        System.out.println("LinkedList 소요 시간 " + (endTime - startTime));

    }
}

 

위와 같이 ArrayList와 LinkedList에서 요소를 추가하는 연산과, 특정 인덱스에 접근하는 연산을

반복문을 통해서 구현했다.

소요시간은 반복문 실행 후의 시간과 반복문 실행 전의 시간을 빼서 구했다.

 

 

결과

요소 추가 소요 시간 : ArrayList > LinkedList

요소 접근 소요 시간 : ArrayList < LinkedList

 

요소를 추가할 때 걸리는 시간은 ArrayList가 더 크고,

요소에 접근할 때 걸리는 시간은 LinkedList 가 더 컸다.

결론

각 List 의 특징에 따라 연산시간이 다르므로

특징을 잘 알아두고 구현하려는 목적에 따라 적절한 자료구조 기반의 List 를 사용해야 한다.

예를 들어 단순히, 어떤 배열 데이터에서 특정 데이터를 찾는 기능만 있다면 ArrayList를 사용하는 것이

연산속도가 더 빠르기 때문에 적절하다.

그러나 어떤 요소를 추가하거나 삭제하는 연산이 있어야 한다면 LinkedList를 사용하는 것이

연산속도가 더 빠르기 때문에 적절하다.

3. 마치며

본 포스팅은 내가 지금 Java 를 배우고 있기 때문에, java를 기반으로 작성했다.

Java에는 연결리스트 기반의 List가 있길래 자바스크립트에도 있나 싶어서 검색해봤는데,

따로 있는거 같지는 않고 class 를 이용해서 기능을 비슷하게 구현한 것만 보였다.

아마 class 도 원래는 없었는데 ES6 로 업데이트 하면서 생긴거니까

연결리스트에 대한 필요성이 자바스크립트에도 느껴지면 업데이트 해주지 않을까...? 생각하고 있다.

그래도 혹시 모르니깐 구현하는 방법에 대해서도 알아봐야 겠다고 느꼈다.

 

아이러니하게도 자바 문법배우면서 자바스크립트랑 비교하게 되서 오히려 둘 다 공부가 되는거 같다...?

 

 

4. Reference

1. 코딩온 강의 교안 및 실습

 

2.  도서 : 그림으로 이해하는 알고리즘

 

그림으로 이해하는 알고리즘 | 이시다 모리테루 - 교보문고

 

3. 코딩알려주는 누나 유튜브

https://www.youtube.com/watch?v=Q2Up3PN0-nM

 

4. https://structuring.tistory.com/152

JAVA 문법 - ArrayList와 LinkedList(메모리 측면 비교)

 

 

5. https://sj0826.github.io/structure/structure-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8/

[자료구조] 연결리스트 (Linked List) by JS