안녕하세요. 이번 포스팅은 자바 컬렉션의 리스트에 대해서 작성해보겠습니다.

그전에 작성했던 포스트 링크 놓고 시작하겠습니다.

 

 

[Java] Collection(1) - 컬렉션 프레임워크

컬렉션 프레임워크란? (Collection Framework)  컬렉션 프레임워크는 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합입니다.다른 말로 설명해보면, 데이터

lumos-maxima-nox.tistory.com

 

 

 

List Collection

List interface를 구현한 모든 리스트 컬렉션은 다음과 같은 특징이 있습니다.

1. 요소의 저장 순서가 유지됩니다.
2. 같은 요소의 중복 저장을 허용합니다.

대표적인 클래스는 다음과 같습니다.

  • ArrayList
  • LinkedList
  • Vector
  • Stack

 

List Method

List collection에서 사용할 수 있는 메서드들입니다.

기능 메서드  설명
객체 추가 boolean add(E e) 주어진 객체를 맨 끝에 추가
void add(int index, E element) 주어진 인덱스에 객체를 추가
set(int index, E element) 주어진 인덱스의 객체를 새로운 객체로 바꿈
객체 검색 boolean contains(Object o) 주어진 객체가 저장되어 있는지 여부
E get(int index) 주어진 인덱스에 저장된 객체를 리턴
isEmpty() 컬렉션이 비어 있는지 조사
int size() 저장되어 있는 전체 객체 수를 리턴
객체 삭제 void clear() 저장된 모든 객체를 삭제
E remove(int index) 주어진 인덱스에 저장된 객체를 삭제
boolean remove(Object o) 주어진 객체를 삭제

 

ArrayList

`ArrayList`는 인덱스를 가진 동적 배열 리스트입니다. 일반 배열과 달리 제한 없이 객체를 추가할 수 있습니다.

인스턴스를 생성할 때 사이즈를 지정해서 배열을 생성할 수 있고 사이즈를 지정하지 않을 시 기본값은 10입니다.

요소를 저장하며 배열이 꽉 차게 되면 새로운 배열을 만들어 기존 값을 복사하는 구조입니다.

`ArrayList`는 데이터 검색 시 배열의 인덱스를 통하여 빠르게 접근할 수 있습니다.

데이터 저장, 삭제 시 하단의 그림과 같이 인덱스를 밀고 당기는 작업을 하게 됩니다.

데이터를 당기는 방식은 `data3`이 삭제되고 `3번 index`에 저장된 값부터 `7번 index`에 저장된 값을 복사 후 `2번 index` 부터 덮어 씌우며 `7번 index`에는 `null` 값을 저장합니다.

배열의 공간이 찬 상태에서 데이터를 인서트 할 때와 데이터를 삭제할 때 배열을 복사하는 과정에서 지연이 발생합니다.

 

따라서 아래와 같은 경우 사용하는 것이 좋습니다.

  • 데이터의 양이 일관적이고 삽입, 삭제가 빈번하지 않은 경우
  • 데이터 읽기 작업이 많고 접근 속도가 중요한 경우

시간 복잡도

  • 검색 : `O(1)` - 어떠한 데이터를 조회해도 성능 일정 (index 사용)
  • 삽입/삭제 : `O(n)` - 데이터가 늘어날수록 작업 시간도 증가
💡 Big O 시간복잡도
    -> 알고리즘의 성능을 나타내는 표기법
성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ) 입니다

 

LinkedList

`LinkedList`는 `ArrayList` 와 사용방법은 동일하지만 내부 구조는 완전히 다릅니다.

`LinkedList`는 `Node`에 의해 데이터들이 연결되어 있습니다. 이를 `연결리스트` 라고 부릅니다.

 

연결리스트에는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List)가 있습니다.

단일 연결 리스트는 각 노드가 다음 요소만 가리키는 리스트이며, 이중 연결 리스트는 각 노드가 이전 요소, 다음 요소 모두 가리키는 리스트입니다.

 

`LinkedList`는 이중 연결 리스트로 구현하며 노드끼리 서로 참조 값을 가지고 있어 삽입/삭제 성능이 우수합니다.

이게 무슨 말이냐,  앞/뒤로 연결되어 있는 주소값(참조값)만 바꾸어주면 삽입/삭제가 가능합니다.

그림과 같이 1-2, 2-3 으로 연결되어 있던 참조 값을 1-3 으로 참조값을 변경하여 데이터를 쉽게 삭제할 수 있습니다.

하지만 특정 데이터를  읽기 위하여 최초 생성 노드로부터 순차적으로 검색해야 하기 때문에 데이터 접근 속도가 느립니다.

 

따라서 아래와 같은 경우 사용하는 것이 좋습니다.

  • 데이터 접근 빈도보다 삽입, 삭제가 많은 경우
  • 맨 앞 또는 맨 뒤 데이터 삭제가 빈번한 경우

시간 복잡도

  • 검색 : `O(n)`
  • 삽입/삭제 : `O(1)` 
💡 Big O 시간복잡도
    -> 알고리즘의 성능을 나타내는 표기법
성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ) 입니다

 

ArrayList vs LinkedList 예제

`ArrayList` 와 `LinkedList`의 데이터 삽입 시 성능을 비교해 보았습니다. 예제는 "이것이 자바다" 책을 참고하였습니다.

각각 정수 데이터를 10만 건을 추가하여 시간을 측정하였고, 중간 데이터를 검색하였습니다. 

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

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

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

        //시작 시간과 끝 시간을 저장할 변수 선언
        long startTime;
        long endTime;

        //Array 데이터 10만개 추가
        startTime = System.nanoTime();
        for(int i=0; i<100_000; i++){
            list1.add(String.valueOf(i));
        }
        endTime = System.nanoTime();
        System.out.printf("%-17s %8d ns \n", "ArrayList add 걸린 시간", (endTime - startTime));

        //LinkedList 데이터 10만개 추가
        startTime = System.nanoTime();
        for(int i=0; i<100000; i++){
            list2.add(String.valueOf(i));
        }
        endTime = System.nanoTime();
        System.out.printf("%-17s %8d ns \n", "LinkedList add 걸린 시간", (endTime - startTime));

        //Array get()
        startTime = System.nanoTime();
        list1.get(53404);
        endTime = System.nanoTime();
        System.out.printf("%-17s %8d ns \n", "ArrayList get 걸린 시간", (endTime - startTime));

        //LinkedList get()
        startTime = System.nanoTime();
        list2.get(53404);
        endTime = System.nanoTime();
        System.out.printf("%-17s %8d ns \n", "LinkedList get 걸린 시간", (endTime - startTime));
    }
}

 

출력 결과
ArrayList add 걸린 시간  8001125 ns 
LinkedList add 걸린 시간  3101917 ns 
ArrayList get 걸린 시간     4750 ns 
LinkedList get 걸린 시간   579375 ns

 

데이터 삽입시간은 `LinkedList`가 두 배 이상 빠른 시간 안으로 작업을 완료했습니다.

`ArrayList`가 느린 이유는 배열이 꽉 찰 때마다 복사를 하여 배열 크기를 늘리기 때문입니다. 

반대로 데이터 검색시간은 `ArrayList`가 압도적으로 빠른 성능을 보여주었습니다.

 

Vector

`Vector`는 `ArrayList`와 동일한 내부 구조를 가지고 있습니다.

차이점은 `Vector` 는 멀티스레드 환경에서 안전하게 객체를 추가할 수 있는 동기화된(synchronized) 클래스입니다.

 

동기화(synchronized)는 하나의 자원에 여러 스레드가 동시에 접근할 때 경합이 일어나지 않도록 잠금을 거는 것을 말합니다.

아래의 그림과 같이 하나의 스레드만 메서드에 접근시킵니다.

 경합은 멀티스레드 환경에서 안전하지 않은 메서드들이 동시에 실행되는 경쟁상태를 의미하며 경합이 일어나면 서로의 실행 결과에 영향을 미치게 되어 원하는 값을 얻지 못할 수 있습니다. 또한 멀티스레드에서 안전하기 위하여 모든 메서드에 잠금을 걸기 때문에 단일 스레드 환경에서는 불필요한 성능 저하가 있을 수 있습니다.

 

`Concurrent Collection(동시성 컬렉션)`이 등장하고서 `Vector` 사용을 지양하고 있습니다. 

시간 복잡도

  • 검색 : `O(1)`
  • 삽입/삭제 : `O(n)` 
💡 Big O 시간복잡도
    -> 알고리즘의 성능을 나타내는 표기법
성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ) 입니다

 

Vector 예제

`vector` 와 `ArrayList` 에 각각 스레드를 2개 돌려 값을 동시에 만 개씩 추가해 보았습니다.

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;
public class VectorExample {
    public static void main(String[] args){
   
        //Vector 컬렉션 생성
        //List<Board> list = new Vector<>();
        List<Board> list = new ArrayList<>();

        //작업 스레드 객체 생성
        Thread threadA = new Thread(){
            @Override
            public void run(){
                //객체 1000개 추가
                for(int i=1; i<=10_000; i++){
                    list.add(new Board("제목"+i,"내용"+i,"글쓴이"+i));
                }
            }
        };
        Thread threadB = new Thread(){
            @Override
            public void run(){

                for(int i=10_001; i<=20_000; i++){
                    list.add(new Board("제목"+i,"내용"+i,"글쓴이"+i));
                }
            }
        };
        //작업 스레드 실행
        threadA.start();
        threadB.start();

        //작업 스레드 들이 모두 종료될 때까지 메인 스레드를 기다리게 함
        try{
            threadA.join();
            threadB.join();
        }catch(Exception e){}

        //저장된 총 객체 수 얻기
        int size = list.size();
        System.out.println(" Vector - 총 객체 수: "+size);
        // 출력 : vector = 20000 / Arraylist = 19289
        System.out.println();
    }
}

 

그 결과, 스레드에 안전한 `Vector`는 데이터 2만 개가 정상적으로 추가되었고, `ArrayList`는 경합이 일어나 19,289개의 데이터만 추가된 것을 확인할 수 있었습니다.

 

Stack

`Stack`클래스는 `Vector` 클래스를 상속받아 구현됩니다.

마지막으로 추가된 요소가 먼저 제거되는 후입선출(LIFO, Last in First Out)의 자료구조입니다.

동기화(Synchronized)가 되어 있어 멀티 스레드에서 안전합니다.

아래는 Stack의 주요 메서드들입니다.

메소드 설명
push(E item) 스택의 맨 위에 요소를 추가합니다.
pop() 스택의 맨 위 요소를 제거하고 반환합니다.
peek() 스택의 맨 위 요소를 반환하되 제거하지 않습니다.
search(Object o) 특정 요소의 1부터 시작하는 위치를 반환합니다. 없으면 -1을 반환합니다.

 

시간 복잡도

  • 검색 : `O(1)`
  • 삽입/삭제 : `O(n)` 
💡 Big O 시간복잡도
    -> 알고리즘의 성능을 나타내는 표기법
성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ) 입니다

 

이렇게 리스트에 대해 알아보았습니다. 

도움이 되셨다면 공감 한 번 부탁드리며 잘못된 정보가 있다면 언제든 댓글 달아주세요!🪄

 

 

⬇️ 참고 URL

https://www.codelatte.io/courses/java_programming_basic/5N27027VT1DBUAX0

이것이 자바다 책
https://www.geeksforgeeks.org/stack-class-in-java/

저작자표시 비영리 동일조건 (새창열림)

'프로그래밍언어 > Java' 카테고리의 다른 글

[Java]Collection(5) -Map  (5) 2024.11.07
[Java]Collection(4) - Set  (0) 2024.11.06
[Java]Collection(3) - Queue, Deque  (0) 2024.11.05
[Java] Collection(1) - 컬렉션 프레임워크  (0) 2024.11.01

티스토리툴바