Array
- 같은 자료형의 구성요소가 직선 모양으로 연속하여 줄지어 있는 단순 자료구조이다.
- 논리적 저장 순서와 물리적 저장 순서가 일치한다.
- 인덱스로 해다 원소 접근이 가능하다
- 찾고자 하는 원소에 대해서 인덱스 값만 안다면 Big-0(1)에 해당 원소로 접근 할 수 있다.
- Stack 섹션에 메모리 할당이 이루어진다.
사용
int[] a;
int a[];
a = new int[5];
a[1] = 37;
a[2] = 40;
...
for(int i=0; i<a.length; i++){
System.out.println(a[i]);
}- new int[5]로 배열 본체를 생성하고 변수 a가 배열 본체를 참조한다.
- 배열에선 특정 원소에 값을 대입하지 않으면 0으로 할당된다.
- 배열 a의 자료형과 a[i](i는 요소의 index값)의 자료형은 다르다는 것.
- 배열 a는 int[5]형 자료형, 총 5개의 int형 저장공간을 차지하는 것.
- a[i]는 int형 자료형.
메서드
- .length : 길이를 구한다.
- .clone() : 배열을 복사한다.
- maxOf(배열이름) : 배열 구성요소 중 최대 값을 구한다.
장점
- Random Access가 가능하다.
단점
- 삭제 or 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤에 또 한가지 작업을 추가적으로 해야하기에 시간이 더 걸린다.
- 예를 들어, 배열 내 특정 원소를 삭제 할 경우, 빈 공간이 생기게 되고 이를 메꾸기 위해 shift를 해줘야하는 cost가 발생하고 이는 시간 복잡도가 O(n)이 된다. 그렇기에 Array 자료 구조에서 삭제 기능에 대한 time complexity의 worst case는 O(n)가 된다.
Linked List
- 순서가 있고 각각의 데이터가 나열되어 있는 형태이다.
- 나열된 불연속적인 데이터를 서로 연결한 형태이다.
- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하고 있다. 이때 리스트의 데이터는 노드, 요소라고 한다.
- Heap 섹션에 메모리 할당이 이루어진다.
array와의 연관성
- array의 단점을 해결한 자료구조가 Linked list이다.
- 각각의 원소들은 자기 자신 다음에 어떤 원소인지만 기억하고 있다.
- 따라서, 이 부분만 다른 값으로 바꿔주면 삭제/상빕을 O(1)만에 해결할 수 있다.
- 데이터 복사, 이동 과정 없이 노드 간 참조 변경만으로 데이터 추가/삭제 가능하다.
단점
- 원하는 위치에 삽입을 하고자 하면, 원하는 위치를 찾는 과정에 있어서 첫 번째 원소부터 다 확인해봐야 한다.
- Array와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치 하지 않기에..
- 일단 삽입하고 정렬하는 것과 마찬가지의 느낌.
- 그래서 어떤 원소를 삭제/추가 하고 할때, 그 원소를 찾기 위해 O(n)의 시간이 추가적으로 발생한다.
linked list의 한계
- 결국 linked list에서도 search에 O(n)의 시간 복잡도를 갖고, 삽입,삭제에 대해서도 O(n)의 시간 복잡도를 갖는다.
- 그렇다고 해서 아주 쓸모 없지는 않다. tree구조의 근간이 되는 자료구조로 tree에서 사용되었을 때 유용하다.
- 다음 노드를 찾기는 쉽지만 앞쪽 노드를 찾을 순 없다. 그래서 이중 연결 리스트가 나와있다.
developer