[자료 구조] Array, Dynamic Array, Linked List

Array

배열(array)는 여러 데이터를 연속된 메모리에 저장할 때 사용하는 자료 구조로, 동일한 자료형의 데이터를 한꺼번에 순차적으로 관리할 수 있게 해준다.

배열의 특징

• 배열은 한번 생성하면 크기를 변경할 수 없다(데이터가 메모리에 정적, 연속적으로 할당됨).
• 배열은 인덱스(메모리 주소 + 순서의 의미)로 접근이 가능하며, 배열 내 데이터 수정이 가능하다.
• 리스트와 비교했을 때, 더 compact하게 메모리 공간을 차지한다.
• 삽입, 삭제 시 원래 데이터 중 평균적으로 n/2만큼 메모리를 옮겨줘야 하기 때문에 O(n)의 시간 복잡도를 가진다.
• 인덱스를 통한 데이터 탐색 시 인덱스에 메모리 주소 정보가 포함되어 있어서 바로 데이터 탐색이 가능하다. 따라서 시간 복잡도는 O(1)이다.
• spacial locality가 보장되기 때문에 cache hit의 가능성이 높아져서 병목 현상이 줄어들어 성능 개선(프로세스를 빠르게 처리)에 도움이 된다.

배열의 한계

• 배열은 길이를 바꿀 수 없다. 길이를 바꾸고 싶다면 (1)새로운 길이의 배열을 메모리에 따로 할당하고 (2)데이터를 복사한 후 (3)기존의 배열의 삭제하는 세가지 과정을 거쳐야 한다. 따라서 리소스 낭비가 크다(비효율적이다).
• 배열은 데이터가 없어도 메모리를 차지하기 때문에, 엘리먼트가 삭제되어도 빈자리(null)가 남게 된다. 따라서 메모리가 낭비된다(inner fragmentation). 조건문을 통해 데이터가 null인 경우 삭제할 수도 있는데, 앞서 언급한 것처럼 데이터 삭제 시 O(n)의 시간 복잡도를 가지기 때문에 비효율적이다. 하지만 데이터 수가 적고, 인덱스가 그 자체로 중요한 의미를 가진다면 배열을 사용할 수도 있다.
• 연속된 메모리에 할당되기 때문에, 메모리 공간이 있음에도 outer fragmentation이 발생할 수 있다.

따라서, 배열은 인덱스가 중요하거나 인덱스를 통한 데이터 탐색이 빈번할 때 효과적인 자료구조이다.

배열 사용 예제

public class ArrayTest {

	public static void main(String[] args) {
		int[] numbers = new int[4];
		int[] numbers2 = { 0, 1, 2 };

		System.out.println(numbers.length);
		System.out.println(numbers2.length);

		for (int i = 0; i < numbers.length; i++) {
			numbers[i] = i + 1;
		}

		for (int i = 0; i < numbers.length; i++) {
			System.out.println(numbers[i]);
		}
	}
}

Dynamic Array

동적 배열(dynamic array)(a.k.a ArrayList)이란 배열의 특성은 가지되, 고정된 길이를 갖는 배열의 한계를 극복하기 위해 나온 자료구조이다.

동적 배열의 특징

• 동적 배열은 크기를 변경할 수 있는 배열이다. 따라서 크기가 고정되어 있는 (static) array만을 사용할 때, 비효율적이거나 한계가 있는 작업을 할 때나 처음부터 배열을 크기를 알 수 없는 경우에 동적 배열을 사용한다.
• 동적배열은 배열과 마찬가지로 데이터들이 연속된 위치에 저장되어 있고 각 데이터에 인덱스로 접근할 수 있다. 하지만 배열의 맨 끝에 데이터를 추가하는 append() or add() 연산 덕분에 길이를 고정하지 않아도 된다. 동적배열의 '재할당 전략'을 통해 append()연산을 시간 복잡도 O(1)에 처리할 수 있다.

1. 배열의 크기를 변경하는 resize() 연산은 시간 복잡도가 O(n)이다.
   • resize() 연산은 새로운 크기의 배열을 만든 후 기존 배열을 복사하는 방식으로 진행되기 때문에 O(n)의 시간 복잡도를 갖는다.
2. 데이터를 배열의 맨 끝에 추가하는 append() 연산은 시간 복잡도가 O(1)이다.
   • 재할당 전략: 데이터가 추가될 때, 배열의 크기를 기존 배열의 크기만큼 늘리는 전략
   • 재할당 전략을 사용하지 않고 데이터의 메모리 크기만큼 배열의 크기를 늘린다면, append()연산을 n번 진행한다고 했을 때 n(n+1)/(2*n)만큼, 즉 O(n)의 시간 복잡도를 가진다. (n + 2n + 3n + ... + n^2)/n = (n+1)/2 = O(n)
   • 재할당 전략을 사용하고 기존 배열에 데이터가 꽉찬 상태에서 데이터가 추가될 때 기존 배열의 크기만큼 배열의 크기를 늘린다면, append() 연산을 n번 진행한다고 했을 때 O(n/n) = O(1)만큼의 시간 복잡도를 가진다. 이는 resize() 연산의 시간 복잡도가 O(n)이고 이를 평균내면 O(1)이기 때문이다.

동적 배열 사용 예제

import java.util.ArrayList;

public class ArrayListTest {

	public static void main(String[] args) {

		ArrayList<String> list = new ArrayList<String>();
		list.add("aaa");
		list.add("bbb");
		list.add("ccc");

		for (String s : list) {
			System.out.println(s);
		}
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
	}
}

Linked List

Linked List는 데이터와 다음 데이터의 메모리 주소(link)를 함께 저장하여 연속되지 않은 메모리를 사용하는 자료 구조이다.

Linked List의 특징

• Linked list에는 다음 데이터의 주소를 가리키는 link 정보도 들어있기 때문에, 연속되지 않은 메모리에 데이터가 할당될 수 있으며, 이로 인해 fragmentation이 발생하지 않는다.
• Link로 데이터를 연결/삭제하기 때문에 list의 크기가 변할 수 있다
• 동적 배열에 비해 효율적으로 데이터를 삽입, 삭제할 수 있다.
  • Head에서 데이터를 삽입/삭제 시 Head 노드의 link만 수정해주면 되기 때문에 시간 복잡도가 O(1)이 된다.
  • Head가 아닌 노드에서 데이터를 삽입/삭제 시, 해당 노드가 무엇인지 안다면 O(1)의 시간 복잡도를 가지고, 모른다면 탐색 후 데이터를 삽입/삭제해야 하기 때문에 O(n)의 시간 복잡도를 가진다.

Linked List의 한계

• 데이터 탐색 시, 평균적으로 (n+1)/2번의 시간이 소요되기 때문에 시간 복잡도가 O(n)으로 비효율적이다.

따라서, Linked List는 데이터의 추가/삭제가 빈번하게 발생할 때 효과적인 자료구조이다.

Linked List 사용 예제

Linked List 데이터 추가

LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1);//가장 앞에 데이터 추가
list.addLast(2);//가장 뒤에 데이터 추가
list.add(3);//데이터 추가
list.add(1, 10);//index 1에 데이터 10 추가

Linked List 데이터 삭제

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5));
list.removeFirst(); //가장 앞의 데이터 제거
list.removeLast(); //가장 뒤의 데이터 제거
list.remove(); //생략시 0번째 index제거
list.remove(1); //index 1 제거
list.clear(); //모든 값 제거

Linked List 크기

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.size()); // 3

Linked List 값 출력

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));

System.out.println(list.get(0));//0번째 index 출력
				
for(Integer i : list) { //for문을 통한 전체출력
    System.out.println(i);
}

Iterator<Integer> iter = list.iterator(); //Iterator 선언 
while(iter.hasNext()){ 
    System.out.println(iter.next());
}

Linked List 값 검색

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.contains(1)); //list에 1이 있는지 검색 : true
System.out.println(list.indexOf(1)); //1이 있는 index반환 없으면 -1