[자료구조] Array와 LinkedList

🌈 m1naworld ·2023년 2월 24일

Array, LinkedList 는 데이터를 저장하고 조작하는데 사용되는 일반적인 자료구조

Static Array

같은 타입의 데이터들을 고정된 연속된 메모리 공간에 저장하는 자료 구조로 각 요소는 인덱스를 사용하여 액세스 가능. 일반적으로 Array라 하면 Static Array를 칭함

장점

요소에 대한 빠른 액세스가 필요할 때 효율적
연속된 메모리 공간에 데이터들을 저장하기 떄문에 cpu cache를 통해 같은 배열에 있는 다른 데이터에 접근하는 시간을 단축할 수 있음

단점

배열의 크기를 변경할 수 없으므로 추가, 삭제 불가능

Dynamic Array

Array의 크기가 동적으로 늘어나 데이터를 추가/저장 할 수 있는 자료 구조로 크기를 초과하는 새로운 요소를 추가하면, 더 큰 메모리 공간을 할당하고 기존 요소들을 복사함
대표적인 예시로는, Python의 List, Js의 Array, Java의 ArrayList 등이 있음

장점

Static Array의 장점 + 크기를 변경할 수 있는 유연성

단점

크기를 변경하는 과정에서 복사 과정이 필요하기 때문에 일부 작업에서 성능 저하 될 수 있음
크기가 변하는 경우 추가 메모리를 할당하기 때문에 추가적인 메모리 사용량 발생

Linked List

Linked List는 노드의 시퀀스로 구성된 비선형 데이터 구조
각 노드는 데이터 요소와 다음 노드를 가리키는 포인터를 포함하며 단일 연결 리스트(각 노드가 다음 노드를 가리킴) 또는 이중연결 리스트(각 노드가 다음 및 이전 노드를 모두 가리킴)가 있음. 따라서 요소를 추가하거나 삭제할 때는 해당 위치 이전의 노드와 다음 노드의 포인터만 변경해주면 되기 때문에 동적배열 보다 삽입 및 삭제가 빠르나, 인덱스로 요소를 접근하는 것이 불가능함

(*노드: 데이터와 링크로 구성된 데이터 저장 단위)

장점