태그 글목록: 원형 리스트

[C++ 정리] 배열(Array)과 연결리스트(Linked List) 2015-06-18

배열 : 정해진 크기만큼만 선언을 할 수 있다. 이는 연결된 메모리를 보장해준다. 하지만 이는 유연하게 프로그래밍을 하는데는 제약이 있다.

array
장점

* 구현이 간단하다.
* 연결된 메모리상에 존재하므로 중간 데이터에 빠르게 접근할 수 있다. 
  ex> array[3] 으로 'D'에 접근할 수 있다.

단점

* 크기를 고정해야 하기 때문에 사용될 것을 고려하여 할당해야 하고 이는 불필요한 메모리를 차지한다.
* 중간 데이터의 삽입 또는 삭제가 일어난다면 뒤에 데이터를 전부 변경해야만(메모리상에서 한칸씩 밀거나 당긴다) 하기 때문에 비효율적이다.

연결리스트 : 크기에 대한 제약없어 유연하게 활용할 수 있지만 연결된 메모리가 아니기 때문에 데이터를 찾기 위해서는 모든 노드를 거쳐서 탐색해야 한다.

linkedlist
장점

* 필요할때마다 메모리를 동적으로 할당하기 때문에 메모리 효율적이다.
* 중간에 데이터를 삽입 또는 삭제 하더라도 다른 데이터에 영향을 주지 않아 효율적이다.
  Ex> 'D'를 삭제하려면 'C'에서의 링크를 'E'로 변경만 하면 된다.

단점

* 구현이 복잡하다.
* 중간의 데이터에 접근하기 위해서는 이전 노드를 모두 거쳐야만 접근할 수 있다.
  Ex> 'D'에 접근하려면 'B', 'C'를 거쳐야만 한다.

연결리스트의 종류

> 단일 연결 리스트(Singly Linked List)

singlylinkedlist

typedef struct node
{
    struct node* next;
    void* data;
}Node;
* 노드가 다음노드를 가리킨다.
> 이중 연결 리스트(Doubly Linked List)

doublylinkedlist

typedef struct node
{
    struct node* prev;
    struct node* next;
    void* data;
}Node;
* 각 노드들이 이전과 다음노드를 가리킨다.
> 다중 연결 리스트(Multiply Linked List)

multiplylinkedlist

typedef struct node
{
    vector<struct node *> pointers;
    void* data;
}Node;
* 각 노드가 2개이상의 노드를 가리킨다.
> 원형 연결 리스트(Circular Linked List)

circularlinkedlist

* 리스트의 마지막 노드가 멀리있는 다른 노드(보통 첫번째 노드)를 가리키고 있는 형태이다.
* 원형 이중 연결 리스트(circular doubly linked list)의 경우는 첫번째 노드의 prev는 마지막 노드를, 마지막 노드의 next는 첫번째 노드를 가리킨다.

<링크 : 위키문서(Linked list)> 참조