Связанные списки проблем

Question

Я пытаюсь научить себя C++, и я действительно запутался со связанными списками. Я читал учебники и смотрел онлайн, но я действительно смущен, как они работают. Я нашел онлайн-упражнение, которое я пытался выяснить, но я никуда не уйду.

Вот файл list.h:

struct node 
{ 
    int val; 
    struct node *next; 
}; 

int length(struct node *); 
void push(struct node **, int); //add to front of list 
void append(struct node **, int); //add to rear of list 
void print(struct node *, int); 

Я с трудом пытается написать функции для длины, нажмите и добавить.

Answer 1

Связанный список - это просто строка из Node классов, вместе с каждым владеющим указателем, адресом которого является следующий класс Node в списке.

Это довольно просто, если вы думаете об этом так:

Coliru: http://coliru.stacked-crooked.com/a/5e71c5e31b58673c

#include <iostream> 

//Proper encapsulation is not included for terseness and clarity 
class Node { 
public: 
    int num; 
    Node* next; 

    Node(int n) : 
     num(n), 
     next(nullptr) { 
    }; 

    ~Node() {} 
}; 

int main() { 
    Node a(0); 
    Node b(1); 
    Node c(2); 
    Node d(3); 
    Node e(4); 

    //String the nodes together, linking like metal chainlinks 
    a.next = &b; 
    b.next = &c; 
    c.next = &d; 
    d.next = &e; 

    //Can you see how the "link" actually works here? 
    //Each Node's "next" pointer points to the next node. 
    std::cout << "Node a: " << a.num << std::endl; 
    std::cout << "Node b: " << a.next->num << std::endl; 
    std::cout << "Node c: " << a.next->next->num << std::endl; 
    std::cout << "Node d: " << a.next->next->next->num << std::endl; 
    std::cout << "Node e: " << a.next->next->next->next->num << std::endl; 

    //What if I were to point e to the start of a? 
    e.next = &a; 

    std::cout << "Node e->next: " << e.next->num << std::endl; 
    //It's node a! 

    //Node e.next is now accessible through the linked list: 
    std::cout << "Node e->next = a.next->next->next->next->next: " << a.next->next->next->next->next->num << std::endl; 

    //Usually people just use a for loop for this type of stuff. 
    //Let's use a lambda function to write one right here: 
    auto index_func = [](Node* head, size_t index) { 
     Node* current = head; 
     Node* next = head->next; 

     for (int i = 0; i < index; ++i) { 
      if (next != nullptr) { 
       //Hey, look at the pointers fly! 
       current = next; 
       next = current->next; 
      } else { 
       std::cout << "Whoops, we hit a null pointer before we got to our index!" << std::endl; 
       break; 
      } 
     } 

     return current->num; 
    }; 

    //This is the same as finding the 6th node in the list (but since it's zero-indexing it's [5]) 
    std::cout << index_func(&a, 5) << std::endl; 

    //We can also continue to do this: 
    std::cout << index_func(&a, 499) << std::endl; 
    //This is me accessing the 500th element, which, since our back links to our head node, it's the 4th node, d. 

    return 0; 
} 

Вы, вероятно, может себе представить другие проделки мы можем сделать со связанными списками, если мы решим, чтобы вставить Node между a или e просто переназначить указатели.

Answer 2

void push(struct node **list, int newVal) { //add to front of list 
    struct node* firstNode = *list; 
    struct node* newNode = (struct node*) malloc(sizeof(struct node)); 
    if (newNode == NULL) abort(); 
    newNode->val = newVal; 
    newNode->next = firstNode; 
    *list = newNode; 
} 

void append(struct node **list, int newVal){ //add to rear of list 
    if (*list == NULL) { 
    push(list, newVal); 
    return; 
    } 

    /* Locate last node in list*/ 
    struct node* curNode = *list; 
    while (curNode->next != NULL) 
    curNode = curNode->next; 

    /* Add a new node at the end of the list */ 
    struct node* newNode = (struct node*) malloc(sizeof(struct node)); 
    if (newNode == NULL) abort(); 
    newNode->val = newVal; 
    newNode->next = NULL; 
    curNode->next = newNode; 
}