어떻게 연결 링크 된 목록으로 돌아갈 수 있습니까?

Question

나는 단독으로 연결된 목록이 있습니다. 목록의 각 노드에서 다음 요소로 이동할 수 있습니다. 이전 요소로 이동하는 것이 가능합니까? 메모리 제약 조건 때문에 이중 연결 목록을 사용할 수 없습니다.

Answer 1

이 접근하는 다음 방법 중 하나를 사용하면 이전 항목을 찾을 때까지 목록을 다시 통과하는 것입니다. 해당 항목이 현재 항목과 같을 때 이전 항목에있을 때를 알 수 있습니다.

의사 C 코드하십시오 단일 연결리스트에게 두 가지를 탐색하기위한

Node* GetPreviousNode(Node* currentNode) 
{ 
    Node* iteratorNode = GetHeadNode(); 
    while (iteratorNode != NULL) 
    { 
     if (iteratorNode->Next == currentNode) 
      return iteratorNode; 

     iteratorNode = iteratorNode->Next; 
    } 
    return NULL; 
} 

Answer 2

이전 요소와 다음 요소를 가리키는 포인터가있는 이중 링크 목록을 사용해야합니다. 단일 링크 된 목록은 단순히 다음 요소를 가리키며 이전 요소를 추적하지 않습니다.

이 시도 : 당신이 단독으로 링크 된 목록을 사용해야하는 경우 http://en.literateprograms.org/Doubly_linked_list_(Java)

Answer 3

이 2 개 가지 방법.

방법 1 : 링크 필드 (구조체)는 실제로 '차이'필드입니다. 링크는 다음 항목의 주소에서 이전 항목의 주소를 뺀 으로 계산되므로 ...

next = 현재 항목의 주소 + 현재 항목의 링크. prev = 다음 항목의 주소 - 현재 항목의 링크.

포인터로 산술 연산을 수행 할 수 있다면 비즈니스가 가능합니다. 그렇지 않다면, 유니온 (C++에서)을 사용하거나 방법 2를 사용해야합니다. 알고리즘 및 데이터 구조 = 프로그램 (Niklaus Wirth - Prentice-Hall 1976 - 19 페이지)

방법 2 : 링크 필드 다음 항목의 주소가 인 이전 항목의 주소의 'exclusive or'(^)입니다. 독점적이거나 그 반대이기 때문에 ...

next = 현재 항목의 주소^현재 항목의 링크. prev = 현재 항목의 다음 항목^링크의 주소입니다.

Answer 4

당신이 단독으로 링크 된 목록에서 주어진 노드 앞에있는의 확신 노드가있는 경우에, 당신은 기능 할 수 있습니다 : -

struct node* prev(struct node* before, struct student_detail* current) 
    { 
     struct student_detail* temp = before; 
     while (temp->next != NULL) 
     { 
      if(temp->next == current) 
      { 
       return temp; 
      } 

      temp = temp-> next; 
     } 
     return NULL; 
    } 

과 같이 사용

example_node = prev(before, example_node); 

머리가 있다면 항상 이전 노드로 사용할 수 있습니다.