많은 수의 데이터를 다룰 때 사용하는 기본적인 자료구조이다.
배열을 구성하는 값 요소와 배열에서의 위치를 가리키는 숫자 인덱스로 구성되며 각 데이터를 인덱스와 1:1 대응한다.
데이터가 메모리 상에 연속적으로 저장된다.
장점
- 인덱스를 통해 데이터에 빠르게 접근 가능 (1번인덱스나 130번 인덱스나 접근시간이 비슷하다)
단점
- 참조 변경시에 기존 참조를 새로운 배열로 바꿔야 한다.
- 미리 최대 길이를 정해서 생성하기 때문에 추가, 삭제가 번거롭다
예를 들어 크기를 변경하는 경우
1. 새로운 배열을 생성
2. 기존 내용을 복사
3. 배열 요소를 변경 후 다시 복사의 과정을 거치게 된다
위 문제들을 해결하기 위해 애초에 큰 배열을 만들면 메모리가 낭비된다.
Array 시간복잡도
접근 | 검색 | 삽입 | 제거 |
---|---|---|---|
O(1) | O(n) | O(n) | O(n) |
LinkedList는 데이터와 링크가 묶여있는 노드를 한 줄로 연결한 방식의 자료구조이며 각 링크는 다음 노드의 참조주소를 담고있다.
class Node{ Node next; //다음 노드 Object obj;// 데이터 }
한 번의 참조 변경으로 데이터의 삭제가 가능하며, 배열과는 달리 데이터 이동이 발생하지 않는다.
데이터의 참조만 변경해주면 기존의 데이터는 자동으로 사라지게 된다.
한 번의 Node 객체 생성과 두 번의 참조 변경으로 데이터를 추가할 수 있다.
단점
LinkedList 시간복잡도
접근 | 검색 | 삽입 | 제거 |
---|---|---|---|
O(n) | O(n) | O(1) | O(1) |
더블리 링크드 리스트
class Node{ Node next; //다음 노드 Node previous; //이전 노드 Object obj;// 데이터 }
앞 뒤로 연결되어 접근성이 좋은 이중 연결 리스트이다.
더블리 써큘러 링크드 리스트
끝과 끝을 연결해준 이중 원형 연결 리스트
ArrayList (배열기반) vs LinkedList (연결기반)
순차적 추가,삭제 →ArrayList
접근시간 → ArrayList
중간에 추가,삭제 → LinkedList