5.연결리스트 6.연결리스트의 응용

리스트와 배열의 차이

리스트 : 일정한 순서의 나열 . 어떤 정의에 의해서 결정된 논리적인 순서의 나열

 

배열: 원소의 메모리 공간의 물리적인 위치를 순서적으로 결정하는 특징 . 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서

 

다음 중 포인터로 구현된 리스트에 대한 설명으로 틀린 것은?

1

 ‘일정한 순서’의 나열

2

어떤 정의에 의해서 결정된 ‘논리적인 순서’의 나열

3

리스트를 포인터로 구현할 경우에는 배열에 비해서 추가적인 메모리 공간이 필요하다. 

4

메모리 공간(주기억 장치, DDR)에서의 물리적인 위치가 논리적 위치와 일치한다.

 

 

typedef struct ListNode {   // 단순 연결 리스트의 노드 구조 정의
    int data;

struct ListNode* link;  // [가]: 다음 노드를 가리키는 포인터     listNode* link;  는 컴파일에러남.  !!!
} listNode;

typedef struct {            // 리스트의 헤드(first) 노드 구조 정의
    listNode* head;
} linkedList_h;

linkedList_h* createLinkedList_h(void) { // 연결 리스트 생성
    linkedList_h* H;
    H = (linkedList_h*)malloc(sizeof(linkedList_h)); // [나]: 메모리 할당
    H->head = NULL;
    return H;
}

 

 

단순연결리스트

이중연결리스트 : 메모리가 추가되었지만 속도가증가

원형연결리스트 : 추가적인 메모리 없고 놀고있는 메모리 활용, 한 노드에서 다른 어떤노드로도 접근 가능