array (배열)

: 고정된 크기를 가진 연속적인 메모리 블럭

image.png

https://upload.wikimedia.org/wikipedia/commons/thumb/3/3f/Array1.svg/330px-Array1.svg.png

장점

메모리 구조가 단순함.

인덱스를 통해 접근 가능함.

단점

삽입, 삭제가 비효율적임.

→ 정해진 크기의 데이터를 저장할 때 주로 사용됨.

linked list (연결 리스트)

: 노드들이 포인터로 연결된 유동적인 형태

각각의 노드는 데이터와 그 다음 노드의 주소를 가짐.

image.png

https://upload.wikimedia.org/wikipedia/commons/thumb/6/6d/Singly-linked-list.svg/330px-Singly-linked-list.svg.png

장점

크기 제한이 없음.

삽입, 삭제가 배열보다 효율적임.

메모리 낭비 줄일 수 있음.

단점

인덱스 접근이 느림. O(n)

포인터를 저장하기 위한 메모리 공간이 추가로 필요함.

단일 연결 리스트

image.png

이중 연결 리스트

image.png

원형 연결 리스트