배열리스트와 연결리스트 비교

사진 한장으로 정리

장단점 비교

배열 기반 리스트의 장점

• 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.

 

배열 기반 리스트의 단점

• 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
• 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

👆 이거 반대가 연결리스트의 장점이다. 메모리를 동적으로 할당해 리스트의 길이를 유연하게 조절할 수 있다.

 

연결리스트의 노드를 표현하는 구조체

typedef struct _node
{
    LData data;
    struct _node *next;
}

 

연결리스트를 의미하는 구조체

(한 프로그램 안에 여러개의 연결리스트가 존재할 수 있으니, 이를 다루는 별도의 구조체를 정의해야함)

typedef struct _linkedList
{
    Node *head;
    Node *cur;
    Node *before;			  //삭제를 돕는 멤버
    int numOfData;			  //저장된 데이터 수 기록
    int (*comp)(LData d1, LData d2) //정렬의 기준을 등록하기 위한 멤버
} LinkedList;