📖자료구조의 특징
📁Array
배열(Array)는 보통 다음과 같이 정의한다.
데이터타입 배열이름[배열길이]
즉, 배열을 선언함과 동시에 데이터 타입과 길이가 결정된다. 따라서 저장할 데이터의 최대 수를 예상하기 어렵거나 길이를 가변적으로 변경해야할 필요가 있는 상황에서는 사용하기에 적절하지 않다. 그러나, 인덱스를 통해 원하는 값을 빠르게 검색할 수 있다는 장점을 가지고 있기도 하다.
반면, ArrayList와 LinkedList의 경우 크기를 가변적으로 변경할 수 있다. Java에서의 ArrayList와 LinkedList는 List 인터페이스를 구현한 Collection 구현체라는 공통점이 있다.
📁ArrayList
Java에서 ArrayList는 java.util 패키지에 포함되어있기 때문에 import문을 작성해야한다.
import java.util.ArrayList;
기본적으로 다음과 같은 구문들로 ArrayList를 생성할 수 있다.
ArrayList list = new ArrayList(); //타입 미설정, Object로 선언 ArrayList<Student> members = new ArrayList<Student>(); //타입 설정, Student객체만 사용 가능 ArrayList<Integer> num = new ArrayList<Integer>(); //타입 설정, int 타입만 사용 가능 ArrayList<Integer> num2 = new ArrayList<>(); //new에서 타입 설정 생략 가능 ArrayList<Integer> num3 = new ArrayList<Integer>(10); //초기 용량(capacity) 지정 ArrayList<Integer> list2 = new ArrayList<Integer>(Arrays.asList(1,2,3)); //생성 시 값 추가
ArrayList list = new ArrayList()와 같이 ArrayList를 생성할 경우, Object 배열을 이용하여 데이터를 순차적으로 저장한다. Object는 모든 객체의 최고 조상 격이므로 모든 종류의 객체를 담을 수 있다. 그러나, 보통 ArrayList 선언 시 타입 지정을 함께 한다.
ArrayList는 내부적으로 데이터를 배열에서 관리한다. 배열에 더 이상 저장할 공간이 없으면 자체적으로 배열의 크기를 늘려 처리한다. ArrayList 또한 인덱스를 통해 데이터 접근이 가능하다.
📁LinkedList
연결리스트(LinkedList)는 불연속적으로 저장된 데이터를 서로 연결(link)한 형태로 구성되어있는 자료구조이다. 각 요소(node)들은 자신과 연결된 다음 요소에 대한 주소값과 데이터로 구성되어있다.
class Node { Node* next; int data; }
노드를 추가하거나 삭제하는 방식으로 구조를 변경할 수 있으므로 ArrayList와 마찬가지로 크기가 가변적이다.
Array, ArrayList와 달리 데이터가 불연속적으로 저장되기 때문에 원하는 데이터에 접근하기 위해서는 처음부터 순차적으로 검색해야 한다.
📖자료구조의 삽입과 삭제
📁Array
배열은 순차적인 데이터의 추가와 삭제에 알맞은 자료구조이다. 배열의 중간에 데이터를 추가하려면 빈 자리를 만들기 위해 기존의 데이터들을 복사하여 새로운 배열에 저장해야 하므로 시간이 많이 걸린다. 삭제의 경우, 마지막에서부터 데이터를 삭제하는 것은 빠르지만 배열 중간에 저장된 데이터를 삭제하려면 마찬가지로 새로운 배열에 나머지 데이터들을 복사해야 한다.
또한, 선언과 동시에 크기가 지정되므로 배열의 크기를 변경하고 싶다면 새로운 배열을 생성하여 데이터를 복사해야 한다. 새로운 배열 생성을 방지하기 위해 충분히 큰 크기의 배열을 생성하는 경우, 메모리가 낭비될 수 있다.
정리하면 다음과 같다.
크기가 정해져 있음
순차적인 데이터 추가 -> 빠름
순차적인(끝에서부터) 데이터 삭제 -> 빠름
비순차적인(배열의 중간) 데이터 추가 및 삭제 -> 느림
📁ArrayList
ArrayList는 Array와 달리 크기가 가변적이다. 더 이상 저장할 공간이 없으면 자체적으로 기존의 ArrayList보다 큰 것을 생성하여 기존의 데이터를 복사하고 새로운 데이터를 저장한다.
ArrayList는 순서와 관계없이 데이터를 추가하고 삭제할 수 있는 기능을 제공한다. 그러나, 중간 순서에 데이터를 추가하거나 삭제하면 다른 데이터들이 자리를 이동해야 하는 것은 Array와 동일하다.
즉, ArrayList는 크기가 가변적이라는 점 외에는 Array와 유사하다고 볼 수 있다.
크기가 가변적임
순차적인 데이터 추가 -> 빠름
순차적인(끝에서부터) 데이터 삭제 -> 빠름
비순차적인(배열의 중간) 데이터 추가 및 삭제 -> 느림
📁LinkedList
연결리스트에서의 데이터 추가 및 삭제는 비교적 간단하다. 추가 또는 삭제될 노드에 대해 이전 순서 노드와 다음 순서 노드를 순서에 맞게 잘 연결해주면 된다.
그러나, 인덱스를 통한 데이터 접근이 불가하기 때문에 데이터를 추가하거나 삭제할 순서까지 접근하기 위해서는 처음부터 순차적으로 데이터를 접근해야 한다. 그렇기 때문에 데이터의 추가 및 삭제 자체는 간단하지만, 순차 검색에 소요되는 시간을 고려해야 한다.
크기가 가변적임
데이터 접근 -> 처음부터 검색해야 하므로 느림
데이터 추가 및 삭제 -> 접근 시간을 제외한 추가 및 삭제 자체는 빠름
