배열 : 정해진 크기만큼만 선언을 할 수 있다. 이는 연결된 메모리를 보장해준다. 하지만 이는 유연하게 프로그래밍을 하는데는 제약이 있다.
장점
* 구현이 간단하다. * 연결된 메모리상에 존재하므로 중간 데이터에 빠르게 접근할 수 있다. ex> array[3] 으로 'D'에 접근할 수 있다.
단점
* 크기를 고정해야 하기 때문에 사용될 것을 고려하여 할당해야 하고 이는 불필요한 메모리를 차지한다. * 중간 데이터의 삽입 또는 삭제가 일어난다면 뒤에 데이터를 전부 변경해야만(메모리상에서 한칸씩 밀거나 당긴다) 하기 때문에 비효율적이다.
연결리스트 : 크기에 대한 제약없어 유연하게 활용할 수 있지만 연결된 메모리가 아니기 때문에 데이터를 찾기 위해서는 모든 노드를 거쳐서 탐색해야 한다.
장점
* 필요할때마다 메모리를 동적으로 할당하기 때문에 메모리 효율적이다. * 중간에 데이터를 삽입 또는 삭제 하더라도 다른 데이터에 영향을 주지 않아 효율적이다. Ex> 'D'를 삭제하려면 'C'에서의 링크를 'E'로 변경만 하면 된다.
단점
* 구현이 복잡하다. * 중간의 데이터에 접근하기 위해서는 이전 노드를 모두 거쳐야만 접근할 수 있다. Ex> 'D'에 접근하려면 'B', 'C'를 거쳐야만 한다.
연결리스트의 종류
> 단일 연결 리스트(Singly Linked List)
typedef struct node
{
struct node* next;
void* data;
}Node;
* 노드가 다음노드를 가리킨다.
> 이중 연결 리스트(Doubly Linked List)
typedef struct node
{
struct node* prev;
struct node* next;
void* data;
}Node;
* 각 노드들이 이전과 다음노드를 가리킨다.
> 다중 연결 리스트(Multiply Linked List)
typedef struct node
{
vector<struct node *> pointers;
void* data;
}Node;
* 각 노드가 2개이상의 노드를 가리킨다.
> 원형 연결 리스트(Circular Linked List)
* 리스트의 마지막 노드가 멀리있는 다른 노드(보통 첫번째 노드)를 가리키고 있는 형태이다. * 원형 이중 연결 리스트(circular doubly linked list)의 경우는 첫번째 노드의 prev는 마지막 노드를, 마지막 노드의 next는 첫번째 노드를 가리킨다.