Program Discussion :: Linked List

#include<stdio.h>

#include<stdlib.h>

 

/* Link list node */

struct Node

{

    int data;

    struct Node* next;

};

 

/* Function to reverse the linked list */

static void reverse(struct Node** head_ref)

{

    struct Node* prev   = NULL;

    struct Node* current = *head_ref;

    struct Node* next;

    while (current != NULL)

    {

        next  = current->next;  

        current->next = prev;   

        prev = current;

        current = next;

    }

    *head_ref = prev;

}

 

/* Function to push a node */

void push(struct Node** head_ref, int new_data)

{

    /* allocate node */

    struct Node* new_node =

            (struct Node*) malloc(sizeof(struct Node));

            

    /* put in the data  */

    new_node->data  = new_data;

                

    /* link the old list off the new node */

    new_node->next = (*head_ref);    

        

    /* move the head to point to the new node */

    (*head_ref)    = new_node;

}

 

/* Function to print linked list */

void printList(struct Node *head)

{

    struct Node *temp = head;

    while(temp != NULL)

    {

        printf("%d  ", temp->data);    

        temp = temp->next;  

    }

}    

 

/* Driver program to test above function*/

int main()

{

    /* Start with the empty list */

    struct Node* head = NULL;

   

     push(&head, 20);

     push(&head, 4);

     push(&head, 15); 

     push(&head, 85);      

     

     printf("Given linked list\n");

     printList(head);    

     reverse(&head);                      

     printf("\nReversed Linked list \n");

     printList(head);    

     getchar();

}

#include <iostream>
#include <cstddef>
/* definition of the list node class */
class Node
{
    friend class LinkedList;
private:
    int _value; /* data, can be any data type, but use integer for easiness */
    Node *_pNext; /* pointer to the next node */    
public:
    /* Constructors with No Arguments */
    Node(void)
    : _pNext(NULL)
    { }    
    /* Constructors with a given value */
    Node(int val)
    : _value(val), _pNext(NULL)
    { }    
    /* Constructors with a given value and a link of the next node */
    Node(int val, Node* next)
    : _value(val), _pNext(next)
    {}    
    /* Getters */
    int getValue(void)
    { return _value; }    
    Node* getNext(void)
    { return _pNext; }
    };
/* definition of the linked list class */
class LinkedList
{
private:
    /* pointer of head node */
    Node *_pHead;
    /* pointer of tail node */
    Node *_pTail;
    
public:
    /* Constructors with a given value of a list node */
    LinkedList(int val);
    /* Destructor */
    ~LinkedList(void);
    
    /* Function to a};

/* definition of the linked list class */
class LinkedList
{
private:
    /* pointer of head node */
    Node *_pHead;
    /* pointer of tail node */
    Node *_pTail;
    
public:ppend a node to the end of a linked list */
    void tailAppend(int val);
    /* Function to reverse the list */
    void reverse();
    
    /* Traversing the list and printing the value of each node */
    void traverse_and_print();
};

LinkedList::LinkedList(int val)
{
    /* Create a new node, acting as both the head and tail node */
    _pHead = new Node(val);
    _pTail = _pHead;
}

LinkedList::~LinkedList()
{
    /*
     * Leave it empty temporarily.
     * It will be described in detail in the example "How to delete a linkedlist".
     */
}

void LinkedList::tailAppend(int val)
{
    /* The list is empty? */
    if (_pHead == NULL) {
        /* the same to create a new list with a given value */
        _pTail = _pHead = new Node(val);
    }
    else
     {
        /* Append the new node to the tail */
        _pTail->_pNext = new Node(val);
        /* Update the tail pointer */
        _pTail = _pTail->_pNext;
    }
}

void LinkedList::reverse()
{
    Node *pTempHead = _pHead, *pRestNodes = NULL, *pNextNode = NULL;
    /* The list is empty? do nothing */
    if (_pHead == NULL)
        return;
    /* The previous head node will act as the tail node after reversing */
    _pTail = _pHead;
    /* Take out the head node and make the reverse list basing on it */
    pRestNodes = _pHead->_pNext;
    
    while (pRestNodes != NULL) {
        /* Step1: Take out the next node */
        pNextNode = pRestNodes;
        /* Step2: Update the pointer of rest nodes after taking out the first */
        pRestNodes = pRestNodes->_pNext;
        /* Step3: Add the taken out node to the new list */
        pNextNode->_pNext = pTempHead;
        /* Step4: Update the new temp head node */
        pTempHead = pNextNode;
        /* Repeat Step 1-4 */
    }
    _pHead = pTempHead;
    _pTail->_pNext = NULL;
}

void LinkedList::traverse_and_print()
{
    Node *p = _pHead;    
    /* The list is empty? */
    if (_pHead == NULL) {
        cout << "The list is empty" << endl;
        return;
    }    
    cout << "LinkedList: ";
    /* A basic way of traversing a linked list */
    while (p != NULL) { /* while there are some more nodes left */
        /* output the value */
        cout << p->_value << " ";
        /* The pointer moves along to the next one */
        p = p->_pNext;
    }
    cout << endl;
}
int main(int argc, const char * argv[])
{
    /* Create a list with only one node */
    LinkedList list(1);
    /* Append 3 nodes to the end of the list */
    list.tailAppend(2);
    list.tailAppend(3);
    list.tailAppend(4);    
    cout << "Before reversing:" << endl;
    getch();
    }