두번째 자료구조 포스팅은 Array, ArrayList, LinkedList 에 대해 알아보자! 기본 중 기본인 내용이지만 난 은근히 헷갈려했던 것 같다 ㅎ,,
배열 Array
(대학교 1학년 3월 이후로 배열을 이렇게 진지하게 마주하는 건 오랜만이다,, 그리운 시절,,, ㅎ,, 돌아가고 싶다 ㅜ)
배열은 메모리 공간에 필요한 크기의 메모리 영역을 미리 잡아놓고 사용하는 자료구조이기 때문에 선언 시 그 크기를 반드시 지정해야 한다.
int array1[5];
string array2[10];따라서 정적인 크기의 데이터를 다룰 때에 적합하고 데이터의 양이 계속해서 늘어난다거나 바뀌는 경우에는 적합하지 않겠다.
또한 데이터를 중간에 넣거나 삭제할 때에도 삽입/삭제된 데이터 이후의 데이터들을 모두 옮겨주어야 하기 때문에 매우 비효율적이라고 할 수 있다.
배열 리스트 ArrayList
위와 같은 배열의 단점을 보완한 ArrayList는 크기를 정해주지 않아도 되는 가변적으로 크기가 변하는 선형 리스트이다.
일반적인 배열과 동일하게 순차 리스트이고 index를 이용해 내부의 객체를 관리하지만 ArrayList는 데이터가 추가되어 저장 용량을 초과하면 자동으로 부족한 만큼 용량을 늘린다.
요소를 추가하면 index 0 부터 차례대로 저장되고 중간의 특정 index에 데이터를 추가하거나 삭제하면 index 이후에 위치한 데이터를 모두 한칸씩 앞뒤로 옮겨주어야 해 비효율적이다.
데이터의 크기가 가변적이고 중간에 데이터를 삽입한다거나 삭제하는 경우가 거의 없는 경우에 적절하다.
연결 리스트 LinkedList
LinkedList 는 연속적인 메모리 위치에 저장되지 않는 선형 구조의 자료구조이다. 연속된 메모리를 사용하지 않기 때문에 포인터를 사용해 메모리들을 연결한다.
배열은 미리 특정한 공간을 할당받아 사용한다면 연결리스트는 필요할 때 마다 데이터를 할당받아 추가하는 구조이다.
연결 리스트의 구성 요소 노드(Node) 는 데이터와 다음 노드의 위치를 가지고 있는 포인터로 구성되어 있다. Node = Data + Pointer
일반적으로 링크드 리스트의 시작이 되는 node는 Head, 마지막 node는 Tail이라고 부른다.
미리 메모리 영역 할당이 필요 없다는 장점이 있지만 데이터와 다음 노드를 가리키는 포인터를 한번에 담을 추가 공간이 있어야 하기 때문에 공간 효율이 좋지 않다는 단점이 함께 존재한다.
또한 특정 데이터를 찾기 위해서는 head 부터 순차적으로 데이터 접근 속도가 느리다는 단점이 있다. 배열에 비해서 리스트 중간에 데이터를 추가하고 삭제하는 과정은 비교적 간단하지만 데이터 연결을 재구성 해야 하는 추가적인 작업 역시 필요하다.
LinkedList 종류
1. 단순 연결 리스트
2. 이중 연결 리스트
- 데이터 앞뒤로 이동 및 탐색이 가능!
3. 원형 연결 리스트
- 마지막 노드의 포인터가 첫번째 노드를 가리킴
Reference
연결 리스트의 개념과 종류
배열 리스트(Array List)
[자료구조] 링크드 리스트(Linked List)
