[알고리즘(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 ]를 참고해 작성하였습니다.