💡 자료구조 카테고리의 글은 내용을 간단하게 압축시킨 정리본을 작성할 예정입니다
📢 CS 관련 더 많은 글과 자료는 All-Rounder-Storage, 성장하는 개발자들의 지식 창고에서 볼 수 있습니다 :)
순차리스트 (Array, ArrayList)
Array
- 미리 할당된 크기만큼 저장공간이 연속적으로 배치되어 있는 같은 타입의 여러 변수들의 묶음
ArrayList
- List의 인터페이스를 구현하므로 데이터의 저장순서가 유지되고 중복을 허용
- Object 배열을 이용해서 데이터를 순차적으로 저장
- null을 포함한 모든 요소 저장을 허용
- n개의 요소를 추가하려면 O(n) 시간이 필요
- 내부에서 elementData(capacity)와 size로 나눠짐
- elementData(capacity) : 배열의 총 용량
- size : 요소(데이터)의 개수
장점
- 순차적으로 값을 저장하기 때문에 데이터를 읽는 속도가 매우 빠름
- 중간 위치가 아닌 맨 뒤의 위치에 데이터를 추가하거나 삭제하는것은 매우 빠름
순차적인 데이터 접근이 빠른 이유
각 요소들이 연속적으로 메모리상에 저장되어 있음
따라서 일일히 데이터 요소를 하나씩 찾아가는 것이 아닌 아래의 간단한 식 만으로도 위치 판별 가능
인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기
단점
- 데이터를 계속 담다가 기존 용량이 넘어가면 속도가 일시적으로 느려짐
- 용량이 꽉차서 용량을 늘려야 될 때는 2배 더 큰 용량의 배열을 생성(size >> 1)하여 기존 배열로부터 복사가 이루어져야 함 → 효율 감소
- 배열의 중간에 위치한 객체를 추가하거나 삭제하면 작업시간이 오래걸림 (시간복잡도: O(n))
- 해당 위치 뒤에 있는 요소들을 전부 자리이동 발생
- System.arraycopy() 라는 다른 데이터의 위치를 이동 시켜주는 함수가 호출됨
주의점
- 중간에 있는 특정 범위의 값들을 삭제할때는 인덱스를 거꾸로(뒤 → 앞) 가면서 삭제해야 함
- 한 요소가 삭제될 때마다 빈 공간을 채우기 위해 나머지 요소들이 자리 이동함 (한칸씩 앞으로)
- 인덱스를 정방향(앞 → 뒤)로 삭제할 경우 엉뚱한 값들이 삭제될 수 있음
- 2, 3, 4 인덱스를 삭제할 경우 → 2, 4, 6 인덱스가 삭제될 듯
연결 리스트 (LinkedList)
링크드 리스트
- 마찬가지로 List의 인터페이스를 구현하므로 데이터의 저장순서가 유지되고 중복을 허용
- 순차 리스트와 내부 구현방법만 다를 뿐 제공하는 기능은 거의 동일
- 이동 방향이 단방향이다
- 배열과 다르게 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태
- 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있음
class Node {
Node next; // 다음 요소의 주소
Object obj; // 데이터
}
더블 링크드 리스트 (이중 연결리스트)
- 해당 자료구조가 Java에서 사용되는 LinkedList 이다
- 단순히 링크드 리스트에서 이전 요소에 대한 참조 변수를 추가한 형태
class Node {
Node next; // 다음 요소의 주소
Node previous; // 이전 요소의 주소
Object obj; // 데이터
}
더블 써큘러 링크드 리스트 (이중 원형 연결리스트)
- 단순히 더블 링크드 리스트에서 첫번째 요소와 마지막 요소를 연결 시킨 형태
장점
- 중간 요소의 추가 및 삭제가 매우 빠르다
- 단순히 삭제하고자 하는 요소의 이전 요소가 다음 요소를 참조하도록 변경하면 됨
- 배열처럼 복사해서 자리 이동시키는 행위가 없음
단점
- 데이터를 읽는 속도가 느림
- 불연속적으로 위치한 각 요소들이 서로 연결(link)된 것이라 처음부터 n번째 데이터까지 차례대로 따라가면서 접근해야됨
주의점
- 단순히 LinkedList가 중간 위치의 요소를 추가 및 삭제 하는것이 빠르다고들 하는데, 실제로 해당 요소의 위치까지 접근하는 시간이 O(n)이기 때문에 마냥 빠르다고만 할 수는 없음
순차 리스트(ArrayList) vs 연결 리스트(LinkedList)
ArrayList | LinkedList | |
데이터 읽기 (접근 시간) | 빠르다 | 느리다 |
순차적인 데이터 추가/삭제 | 빠르다 | 느리다 |
중간 데이터 추가/삭제 | 느리다 (copy → 이동) | 빠르다 (접근 시간때문에 마냥 빠르진 않다) |
마무리
ArrayList의 중간 요소를 추가/삭제 하는것이 O(n)이다.
LinkedList가 중간 요소를 추가/삭제하는 것이 시간 복잡도가 1이지만 실제로는 해당 요소까지 접근하는 것이 O(n)이다.
그렇다면 어떤 상황에서 무엇을 선택해야 하는 것일까?
단순히 속도로 보지 말고 효율적인 메모리 용량 관점에서 바라보면 아래와 같을 것 같다.
다루고자 하는 데이터의 양이 변하지 않고 예측 가능한 경우라면, 또한 데이터 접근을 자주 하는 경우라면 용량을 넉넉하게 선언한 ArrayList를 사용하는 것이 제일 좋은 선택이며, 데이터 개수의 변경이 잦을 경우는 LinkedList를 사용하는 것이 현명해 보인다.
📢 자료가 도움이 되셨다면 All-Rounder-Storage, 성장하는 개발자들의 지식 창고로 놀러오세요!
Reference
💡 잘못된 내용이나, 보충할 내용이 있다면 언제든지 편하게 연락 주시면 감사하겠습니다 :)
🙋🏻♂️ Call me
Email : dev.gibeom@gmail.com
KakaoTalk : https://open.kakao.com/me/beomdrive