CS - Data Structure - Array, Linked List

1. Array

배열

 

 

 

가장 기본적인 자료구조로 연속적으로 할당된 메모리에 데이터가 선형으로 저장되어있는 형태.

 

비슷한 타입의 데이터들이 모여 저장되는 경우가 많다.

 

각 데이터 요소는 인덱스를 통해 참조 가능하다.

 

[ 장점 ]

 

1. 배열에 저장된 요소를 탐색하기 편하고 정렬시키기 편하다

 

2. 다수의 값을 처리하기 가장 좋은 자료구조

 

3. 한 개의 변수에 다수의 데이터를 저장하기 좋다

 

 

2. Linked list

 

연결 리스트

 

연결 리스트는 노드들이 연속적으로 연결된 자료구조

노드는 두 가지 요소로 이루어지는데, 하나는 데이터를 저장하는 장소, 다른 하나는 다음 노드를 가리키는 포인터이다.

연결 리스트의 노드들은 메모리 위에 연속된 상태가 아닌 흩어져 저장되어 있을 수 있다.

 

 

 

연결 리스트의 마지막 노드의 포인터는 null을 가리킨다.

 

배열의 단점으로는

 

1. 배열의 크기를 사용전에 알아야함

2. 배열의 크기를 늘리는 일은 실행 시(런타임)에 불가능

3. 배열의 모든 요소는 메모리상에 연속적으로 저장되어야함. -> 새로운 요소를 삽입하는 경우 삽입 이후의 요소를 모두 옮겨야함

 

링크드 리스트의 장점 

 

1. 새로운 요소 삽입 편리. 삽입 이후의 요소들을 옮길 필요없이 포인터만 수정하면된다.

2. 크기가 가변적. 새로운 요소 추가시 크기를 동적으로(실행 시에) 키울 수 있다. 

3. 메모리에 불연속적으로 저장하여 메모리의 모든 공간 활용 가능

4. 메모리 재사용 뛰어남