- 여러 데이터를 그룹화 해서 element로써 관리하기 위한 자료구조
Array
출처 : https://opentutorials.org/module/1335/8677
- Array 선언 시 고정된 크기의 메모리를(길이를) 할당한다.
- 선언시 정해진 메모리(길이)는 변하지 않는다.
- Array는 같은 자료형의 element만 포함할 수 있다.
- Array의 index는 각 value에 대한 유일한 식별자이다. (0부터 시작) 단순히 몇 번째인지를 나타내는 List의 index와는 다르다.
- 이 고정된 index를 사용해서 데이터에 대한 빠른 접근과 수정이 가능하다. (시간복잡도 O(1) )
- Array 중간의 데이터를 삭제하면 삭제된 데이터의 index 위치에 그대로 빈 메모리가 생긴다. (메모리 낭비)
- 빈 메모리를 없애기 위해서는 빈 곳의 index+1 부터 한 칸씩 앞으로 재할당해줘야한다.
출처 : https://opentutorials.org/module/1335/8677
- Array 중간에 데이터를 삽입하는 경우 원래 index 위치의 원소부터 한 칸씩 뒤로 재할당 해줘야 한다.
List
출처 : https://opentutorials.org/module/1335/8636
- List 는 Array와 달리 동적으로 크기를 조정할 수 있다. 데이터를 추가하고 삭제, 수정, 조회하기 위한 다양한 메소드들을 지원한다.
- 배열의 장점인 고정된 index 대신 메모리의 빈틈 없이 데이터를 저장하는 방식을 채택했다.
출처 : https://opentutorials.org/module/1335/8636
- 서로 다른 자료형의 element를 포함할 수 있다.
//Python
my_list = [1, "Hello", True, 3.14]
//Java
List<Object> myList = new ArrayList<>();
myList.add(1);
myList.add("Hello");
myList.add(true);
myList.add(3.14);
- List interface를 구현한 List Collection Class에는 ArrayList, LinkedList, Stack, Vector 등등이 있다.
ArrayList
- 내부적으로 Array를 사용한다.
- 데이터의 추가/삭제의 경우 임시 Array를 생성해 데이터를 복사한다.
- 따라서 대량의 데이터를 추가/삭제하는 경우, 그만큼 복사가 많이 일어나게 되어 성능 저하가 일어날 수 있다. 즉, add() 메서드 실행 시, 더 큰 용량의 배열을 만들어 데이터를 옮기는 것이다.
출처 : https://devlog-wjdrbs96.tistory.com/64
- 하지만 index를 갖고 있어 검색 등 데이터에 접근하는 작업에 더 효율적이다. Array와 마찬가지로 O(1)의 시간복잡도를 갖는다.
LinkedList
출처 : https://devlog-wjdrbs96.tistory.com/64
- 데이터를 각 노드에 저장하여, 각 노드가 다음 노드의 상태만을 알거나(단방향) 이전과 다음 노드의 상태만을 알고 있는 것(양방향)을 말한다.
- 검색 시 맨 처음(Head)부터 모든 노드들을 탐색해야 하기 때문에 최악의 경우 O(n)의 시간복잡도를 가질 수 있다. 따라서 검색에 있어서는 ArrayList보다 비효율적이다.
- 하지만 데이터의 삽입, 삭제시에는 훨씬 빠르다. 해당 노드를 참조하는 이전노드와 다음노드의 포인터 상태를 바꾸면 되기 때문이다.
