연결리스트, 혼란

Question

하여 if 문의 다른 부분에서 꼬리에 추가 2008 C

은 내가이 연결리스트에 대해 이해할 수없는 것은

비주얼 스튜디오.

머리와 꼬리가 지정 될 때 node_temp의 메모리 주소는 tail과 head 모두에 대해 동일한 메모리 위치를 가리 킵니다.

그러나 else 부분은 사실 꼬리를 가리키는 머리입니다. 설명 할 수없고 else 부분에 대해 이해할 수없는 것이 있습니다.

나는 나를 위해 더 잘 설명 할 수 있기를 바랍니다. 링크 된 목록에 추가 할 때 머리가 변경되지 않기 때문에

static struct convert_temp 
{ 
    size_t cel; 
    size_t fah; 
    struct convert_temp *next; 
} *head = NULL, *tail = NULL; 

/** Add the new converted temperatures on the list */ 
void add(size_t cel, size_t fah) 
{ 
    struct convert_temp *node_temp = NULL; /* contain temp data */ 

    node_temp = malloc(sizeof(*node_temp)); 

    if(node_temp == NULL) 
    { 
     fprintf(stderr, "Cannot allocate memory [ %s ] : [ %d ]\n", 
      __FUNCTION__, __LINE__); 
     exit(0); 
    } 

    /* Assign data */ 
    node_temp->cel = cel; 
    node_temp->fah = fah; 
    node_temp->next = NULL; 

    if(head == NULL) 
    { 
     /* The list is at the beginning */ 
     head = node_temp; /* Head is the first node = same node */ 
     tail = node_temp; /* Tail is also the last node = same node */ 
    } 
    else 
    { 
     /* Append to the tail */ 
     tail->next = node_temp; 
     /* Point the tail at the end */ 
     tail = node_temp; 
    } 
} 

Answer 1

처음으로 요소를 추가하면 (A이라고 함) head은 null이고 사용자는 if 부분을 거칩니다. 즉, head과 꼬리는 첫 번째 요소를 추가 할 때 A을 가리 키도록 설정됩니다.

이제 다른 요소 B을 추가해 보겠습니다. 이번에는 head이 null이 아니므로 else 부분을 통과하고, 을 가리 키도록 tail을 설정하고 을 가리키는 것은 A을 가리키고 있습니다. 예상대로

이, 당신은 지금 head이 A를 가리키는 A이 B를 가리키는 아무것도 (널)과 tail 가리키는 B에 B를 가리키는 가지고있다.

단계별로 살펴 보겠습니다.

Initial state: head -+-> null 
         | 
       tail -+ 

Insert item A: head -+-> A ---> null 
         | 
       tail -+ 

Insert item B: head ---> A -+-> B ---> null 
          | 
       tail --------+ 

Insert item C: head ---> A ---> B -+-> C ---> null 
            | 
       tail ---------------+ 

그런 다음 꼬리 포인터가 포인트로 업데이트됩니다 (이미 다음 노드에 대한 NULL을 가리키는) 현재의 꼬리가 새 노드를 가리 키도록 설정되어 있는지 (초기 제외) 각 단계에서 볼 수

new 마지막 노드.

사실의도 더 자세히 C의 추가 (라인으로 라인)을 통해 가자 그래서 당신은 코드의 각 라인은 (난 그냥 포맷에 도움이 node-node_temp 이름을 변경 한) 무엇을하는지 볼 수 있습니다 :

Starting state:    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node = malloc(sizeof(*node)); node ---> C ----------> ? 
(allocate node C)    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node->next = NULL;    node ---> C --------+ 
(ignore payload cel/fah       | 
    for now since it's not  head ---> A -+-> B -+-> null 
    relevant to the list     | 
       structure)  tail --------+ 

tail->next = node;    node ---------------+ 
(first in else clause)       | 
           head ---> A -+-> B -+-> C ---> null 
              | 
           tail --------+ 

tail = node;     node ---------------+ 
(second in else clause)       | 
           head ---> A ---> B -+-> C ---> null 
                | 
           tail ---------------+ 

그리고 결국은 지역 변수이기 때문에 node가 사라지고 당신은 당신의 최종 상태를 가지고 :

       head ---> A ---> B -+-> C ---> NULL 
                | 
           tail ---------------+ 

유지의 장점단일 링크 된 목록의 포인터는 끝까지 항목을 추가하려고 할 때 전체 목록을 단계별로 탐색하지 않아도되도록하는 것입니다.

전체 목록을 가로 지르면 O(n) 시간 작업을 수행합니다 (소요 시간은 목록에있는 항목 수에 따라 다릅니다). tail 포인터를 사용하면 O(1) 시간 작업 (목록 크기와 관계없이 동일한 시간)이됩니다. 제쳐두고, 이중 연결리스트는 tail 포인터에 대한 별도의 사용이 있기 때문에

은 - 신속 tail를 사용하여 시작에 목록의 끝에서 순회를 시작하는 능력과 head 대신에 prev 포인터를 제공합니다 포인터는 next입니다.

Answer 2

는 다른 부분은,리스트의 tail를 업데이트합니다.

꼬리 요소에 대한 포인터를 버퍼링하는 것이 최적화되어 있으므로 각 추가시 헤드의 전체 목록을 단계별로 수행 할 필요가 없습니다.

Answer 3

아직 꼬리를 가리키는 머리가 아닙니다. 머리가 전 꼬리를 가리키고 있습니다. 목록에 하나의 요소 만 포함 된 경우 머리와 꼬리 모두였습니다. 새 노드가 추가되면 꼬리 포인터가 업데이트됩니다. 헤드 포인터가 여전히 올바른 첫 번째 노드를 가리 킵니다.

Answer 4

첫 번째 호출에서 add, head 및 tail은 새로 생성 된 메모리 블록을 가리 킵니다. 모든 후속 호출은 기본적으로 이전 테일 -> 다음을 수정하여 새로운 메모리 블록을 가리키고 나머지는이 새로운 메모리 블록을 가리 키도록 업데이트함으로써 나머지 부분으로 넘어갑니다 .

효율적인 추가 방법입니다. head 만 사용했다면 새로운 node_temp를 추가 할 때마다 이전에 추가 된 node_temp에 도달 할 때까지 (다음 포인터가 NULL이 될 때까지) 머리부터 시작하여 다음 포인터를 모두 따라 가야합니다. 그런 다음 새 노드를 추가하십시오 . 그러면 위의 O (1) 대신 O (n) 알고리즘이됩니다.