[알고리즘(Algorithm)] 3. 배열(Array)과 리스트(List)
기본 *자료구조인 배열(array)과 리스트(list)는 가장 흔히 사용되는 자료구조이다. 하지만 이 둘은 비슷하면서도 분명한
차이점을 가지고 있기에, 이에 대한 이해가 필요하다.
* 자료구조(Data Structure)
컴퓨터가 데이터를 효율적으로 다룰 수 있게 도와주는 데이터 보관에 대한 방법과 연산의 총체를 말한다.
예를 들면 자주 사용하는 데이터 타입인 int도 자료구조이다.
* int의 보관 방법 및 연산
| 보관 방법 | 32bit 메모리 공간 안에 수를 할당하되, 첫 비트를 부호 표현에 사용한다. |
| 연산 | 덧셈(+), 뺄셈(-), 나눗셈(/, %), 곱셈(*), 논리(&&, ||, &, |, ^, !), 시프트(<<, >>) 등의 다양한 연산 제공 |
자료구조는 단순 자료구조(Primitive Data Structure, 또는 기본형)와 복합 자료구조(Non-Primitive Data Structure)로 나뉜다.
또 복합 자료구조는 선형 자료구조(Linear Data Structure)와 비선형 자료구조(Non-Linear Data Structure)로 나뉜다.
이때, 오늘 학습하고자 하는 배열과 리스트는 선형 자료구조에 해당 된다.
[ 참고 및 출처 : 한빛출판네트워크 - 개발자는 반드시 자료구조와 알고리즘을 배워야 할까? ]
※ 배열(Array)
동일한 자료형(Data Type)의 데이터를 연속된 공간에 값을 채워넣는 형태의 자료구조이다.
인덱스(Index)를 통해 참조(Reference) 가능하다는 특징이 있다.
// Java에서의 배열 선언
// 선언시, 데이터 생성
// (1) 자료형[] 변수 = {값1, 값2, 값3 ... };
String[] arr = {"가", "나", "다", "라", "마", "바"};
// 선언 후, 데이터 삽입
// (2) 자료형 [] 변수 = new 자료형[배열 크기];
String[] arr = new String[6]; //크기가 6인 배열 생성
// index를 통해 접근함.
arr[0] = "가";
arr[1] = "나";
arr[2] = "다";
arr[3] = "라";
arr[4] = "마";
arr[5] = "바";
* 배열의 특징
① 인덱스(index)를 사용하여 값에 접근할 수 있다.
② 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.
삽입 / 삭제시, 해당 인덱스 주변에 있는 데이터를 이동시키는 과정이 필요하다. (번거로움)
③ 배열의 크기는 선언할 때 지정할 수 있으며, 변경할 수 없다. (불변성)
④ 구조가 간단하여 코딩 테스트 및 실무에서 많이 사용된다.
⑤ 같은 종류의 변수만 선언 가능하다. (같은 데이터 타입의 모음)
※ 리스트(List)
값과 포인터(pointer)를 묶은 노드(node)를 포인터로 연결한 자료구조이다.
이는 배열이 가지고 있는 인덱스(index)라는 장점을 버림으로써, 데이터를 빈틈없이 채우고 활용하는 장점을 가져왔다.
* 배열의 메모리 낭비?
배열의 가장 큰 특징은 인덱스(index) 구조이다. 이러한 인덱스를 알고 있다면, 데이터를 매우 빠르고 쉽게 가져올 수 있다. 하지만 배열에는 분명한 단점이 있다. 이는, 데이터에 인덱스의 값이 고정되어 있어야 한다는 것이다.
즉, arr[0] 이 5라면, 데이터(5)에 인덱스([0])값이 고정되어 있다는 것이다. 이러한 구조는 삭제시에 해당 공간을
빈공간으로 남겨둬야 하기에 메모리의 낭비를 초래할 수 밖에 없다.
// List 선언
List<String> list1 = new ArrayList<>(100);
List<String> list2 = new ArrayList<>();
ArrayList<String> list3 = new ArrayList<>();
* 리스트(List) 특징
① 인덱스(Index)가 없으므로 값에 접근하려면 Head -> Tail 포인터 순서대로 접근하여야 한다. (속도가 느리다.)
② 포인터로 연결되어 있어, 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
③ 크기가 별도로 정해져있지 않으며, 크기가 변하는 데이터를 다룰 수 있다.
④ 포인터를 저장할 공간 또한 필요하므로, 배열보다 구조가 복잡하다.
* 해당 포스팅은 Infrean의 [ 하루코딩 - Do it! 알고리즘 코딩테스트 with java ]를 참고해 작성하였습니다.