(25.01.05) Array vs ArrayList vs LinkedList

Java에서 배열(Array)은 여러 데이터를 한 객에 안에 넣어서 다룰 때 사용할 수 있다.

그러나 배열은 정해진 크기만큼의 데이터만 넣을 수 있기 때문에 사용에 제약이 따른다.

그럴  때 사용할 수 있는게 ArrayList와 LinkedList인데 이 세가지의 차이를 이번에 알아보자.

 

1. Array

int[] ar = new int[3]; // 1차원 배열(size : 3)
int[][] ar = new int[3][3]; // 3*3 2차원 배열

가장 기본적인 다중 데이터 삽입 객체로써, 특정 자료형들이 메모리 공간 상에서 연속적으로 이뤄진 참조형 자료 구조다.

이 '배열'의 저장 순서는 논리적 저장 순서 = 물리적 저장 순서임을 명시하며, 인덱스(Index)로 해당 원소(Element)에 접근할 수 있다. (ex. int index = 3; ar[3] = 3;)

삭제 및 삽입 시 들어가는 시간복잡도는 O(1) ~ O(n)까지 가질 수 있으며, 선언 시 크기와 타입이 지정 및 고정되기 때문에 변경이 불가능하다. 즉, 검색에는 편할 수 있지만 시간복잡도를 따져보면 검색에 비효율적일 수 있다.

 

2. ArrayList

import java.util.ArrayList;

public class test {

	public static void main(String[] args) {
    	ArrayList<Integer> list = new ArraytList<Integer>();
        list.add(1); // {1}
        list.add(2); // {1,2}
        list.add(3); // {1,2,3}
        
        list.set(1,4); // {1,4,3}
        list.get(1); // 4 출력
        

        
        list.remove(0); // {4,3}
        list.remove(list.size()-1); // list.size == 2 >>>> list.remove(1)  > list : {4}
    
    }
}

 

크기가 고정된(== 정적인) 다중 데이터 삽입 객체인 Array를 보완한 자료구조로써, 별도로 크기를 지정해주지 않아도 된다.

또한 데이터의 추가 및 삭제 시 Array의 문제점을 해결해줄 수 있다.

(※ Array의 문제점??)

// 1. 데이터 추가
int[] ar = new int[3];

ar[0] = 1;
ar[1] = 2;
ar[2] = 3;
ar[3] = 3; // 에러 발생 : Array는 고정된 크기의 자료형이기 때문에 새 데이터를 추가할 수 없음

// 2. 데이터 삭제
// Array는 데이터 삭제가 불가능함

 

 

그러나, 해당 자료구조는 데이터 삭제에 시간이 오래 걸린다는 문제가 존재한다.(기본적으로 O(N) 고정)

Array와 동일하게 Index로 데이터를 검색할 수 있으며, 특정 인덱스에 데이터를 추가하고자 하면 그 앞에 있는 데이터나 뒤에 있는 데이터의 순서에 영향을 미칠 수 있음(밀리거나 당겨지거나...)

 

 

3. LinkedList

한 노드에 연결될 노드의 포인터 위치를 가리키는 방식의 배열 객체

단일 링크드 리스트와 다중 링크드 리스트가 존재한다

(※ 단일 : 뒤의 노드만 가리키고, 다중 : 앞뒤의 노드를 모두 가리킨다는 차이가 있음)

- 데이터의 중간에 삽입 및 삭제하는 명령에 대해 ArrayList에 비해 낮은 시간복잡도를 가진다(O(1)). 다만, 삭제 및 삽입을 위한 노드를 따로 찾아야 하는 경우엔 O(n)이 되기도 한다.

(※ 검색은 O(n))