[자료구조] 배열(Array), 리스트(List)

자료구조

[자료구조] 배열(Array), 리스트(List)

menuhwang 2022. 11. 8. 14:04

배열과 리스트

개요

처음으로 공부한 자료구조는 배열과 리스트다. 자료구조 공부는 처음이라 어떻게 공부하면 좋을지 어떤것을 공부하면 좋은지 고민해보았다. 각 자료구조들의 특징, 동작원리 등을 알아보고 구현해보는 방향으로 공부를 진행했다.
배열과 리스트는 선형적으로 데이터를 저장하는 자료구조이다. 비슷한 두 자료구조 각각의 특징과 동작원리를 알아보고 차이점을 찾아보자.

배열

용어

인덱스 (index) : 배열에 담긴 요소, 위치에 접근하기 위한 키
요소(element) : 배열에 담긴 단위 데이터

특징

순서 보장, 중복 가능
배열은 메모리 공간을 예약/할당하기 위해 길이를 미리 알려줘야만 한다.
크기 변경에 유연하지 못 하다.
Random Access

선언

public class DataStructure {
    public static void main(String[] args) {
        int[] arr1 = new int[5];
        int[] arr2 = {1, 2, 3, 4, 5};
    }
}

Read

배열에 담긴 데이터를 가져올때 인덱스로 그 위치의 값을 가져올 수 있다.

public class DataStructure {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(arr[2]);
      }
}

따라서, 배열의 데이터 접근, 읽기 시간 복잡도는 O(1) 이다.

Write

값을 추가할때는 인덱스 위치에 값을 넣어준다. 만약 그 위치에 이미 값이 있다면 덮어쓰게 된다.

public class DataStructure {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        arr[0] = 6;
      }
}

쓰기 역시 값을 특정 위치에 쓰기만 하면되기 때문에 시간 복잡도는 O(1) 이다.

Delete

값을 삭제하고 빈 공간을 그대로 두면 되기때문에 시간 복잡도는 O(1) 이다.

Write(Insert)와 Delete를 어떻게 하느냐에 따라 O(N)의 시간 복잡도를 가질 수 있지만 그 내용은 리스트에서 다루도록 한다.

Search

배열은 특정 값이 있는지 없는지 모른다. 따라서, 검색하기 위해서는 배열에 담긴 값을 하나하나 꺼내서 확인해야 한다.
이렇게 순차적으로 모든 요소를 확인해 검색하는 방식을 선형 검색이라고한다.
최악의 경우 찾는 값이 없거나 마지막 위치에 있다면, 모든 값을 열어봐야될 것이다.
그렇기 때문에 배열 내 검색(선형 검색(탐색))의 시간 복잡도는 O(N) 이다.

리스트

특징

순서 보장, 중복 가능
크기가 유동적이다.

ArrayList

특징

배열의 단점인 고정된 크기를 보안한 자료구조.
크기가 유동적임.
Random Access

선언

public class ArrayListPrac {
    public static void main(String[] args) {
    	List<Integer> arrayList = new ArrayList<>();
    }
}

Read

배열과 마찬가지로 인덱스로 그 위치의 값을 가져올 수 있다. 시간 복잡도 O(1)

public class ArrayListPrac {
    public static void main(String[] args) {
    	List<Integer> arrayList = new ArrayList<>();
        // 값 추가 생략
        System.out.println(arrayList.get(0));
    }
}

Insert

리스트에 값을 추가할때 삽입하는 위치의 뒷 요소들을 전부 한 칸씩 뒤로 미뤄야한다.

최악의 경우 0번 인덱스에 추가하면 모든 요소를 움직여야한다.

리스트에서 요소 추가의 시간 복잡도는 O(N) 이다.

public class ArrayListPrac {
    public static void main(String[] args) {
    	List<Integer> arrayList = new ArrayList<>();
        arrayList.add(5);
        arrayList.add(0, 1); // 0번 인덱스 위치에 1을 추가.
    }
}

Delete

삭제의 경우도 삽입과 마찬가지로 다른 요소를 한 칸씩 움직여야한다.

삭제한 요소의 빈 공간을 메우기 위해 뒤에 있는 요소들을 한 칸씩 당겨줘야한다.

따라서, 시간 복잡도는 O(N) 이다.

public class ArrayListPrac {
    public static void main(String[] args) {
    	List<Integer> arrayList = new ArrayList<>();
        // 값 추가 생략
        arrayList.remove(0); // 0번 인덱스 데이터 삭제
    }
}

Search

검색도 배열과 같이 하나씩 열어서 데이터를 확인해야하기 때문에 O(N) 의 시간 복잡도를 가지고 있음.

public class ArrayListPrac {
    public static void main(String[] args) {
    	List<Integer> arrayList = new ArrayList<>();
        // 값 추가 생략
        arrayList.indexOf(3);
        // 리스트에서 3 이란 값을 찾아 있으면 데이터의 위치(인덱스)를 반환.
        // 없는 경우 -1 반환.
    }
}

LinkedList

특징

다음 데이터의 위치를 더 중요시 함.
Sequential Access

Array와 ArrayList와 다르게 데이터를 메모리에 연속적으로 저장하는 것이 아니라 랜덤한 위치에 저장해두고 다음 데이터의 위치가 어딘지 알고 있음.

선언

public class ArrayListPrac {
    public static void main(String[] args) {
    	List<Integer> arrayList = new LinkedList<>();
    }
}

Read

인덱스로 값을 가져오는 ArrayList와 반대로 LinkedList는 인덱스로 값에 한 번에 접근할 수 없다.
따라서 그 인덱스까지 순서대로 찾아가야한다.
3번째 데이터에 접근하고 싶다면 첫 번째 노드에 접근해 다음 노드의 위치가 어디인지 파악해서 3번째 노드에 접근할때까지 순차적으로 노드에 접근해야한다.
이것은 Sequential Access라고 한다.
시간 복잡도는 O(N) 이 된다.

Insert

LinkedList에 데이터를 추가하려면 새로운 노드를 만들고 노드들 사이의 연결을 수정해주기만 하면 된다.

1 -> 2 -> 3 데이터에서 1과 2사이에 4를 추가하고 싶다면 4가 담긴 노드를 생성하고 1 노드 다음에 올 노드의 위치를 4로 변경하고 4 다음 노드 위치를 2로 연결해주기만 하면된다.

이렇게 추가할 위치를 안다는 전제하에 O(1) 의 시간 복잡도를 갖고, 만약 추가할 위치를 모른다면 그 위치에 도달하기 위해 O(N) 의 시간 복잡도를 갖는다.

Delete

이 역시도 노드의 연결만 수정해주면 되기때문에 시간 복잡도는 O(1) 이다. (위치를 알고 있는 경우.)

Search

탐색, 검색은 Array, ArrayList 모두 하나하나 데이터를 꺼내 확인해봐야하기 때문에 시간복잡도는 O(N) 이다.

정리

Array, List 공통

중복된 데이터 허용.
순서가 있음.

Array

크기가 고정되어 있음. (정적이다.)

List

크기가 유동적이다.

ArrayList

인덱스로 값을 가져올 수 있기때문에 데이터 접근이 빠름.
추가나 삭제는 오래걸림.

LinkedList

인덱스로 값을 가져올 수 없어, 순차 접근하기 때문에 데이터 접근이 느림.
추가나 삭제가 빠름.