Doubly Linked List – Implementation in C/C++

31
25



See complete series on data structures here:

In this lesson, we have implemented doubly linked list data structure in C. We have written basic operations for traversal and insertion.

See source code here:

Lesson on Dynamic memory allocation:

For practice problems and more, visit:

Like us on Facebook:

Follow us on twitter:

Nguồn:https://wijstaanvooronzegrondrechten.org/

31 COMMENTS

  1. sir i implement function for the insertion at nth position,in forward function it print but in the case of reverse print it doesn't print the element of nth insertion
    InsertAtN(int x,int n)

    {

    Node* temp = GetNewNode(x);

    Node*temp1 = head;

    for(int i = 0; i<n-2; i++)

    {

    temp1 = temp1->next;

    }

    temp->next = temp1->next;

    temp->prev = temp1;

    temp1->next = temp;

    Node* temp2 = temp->next;

    temp2->prev = temp1;

    }

  2. Hi i want to create a singly linked list in C with 4 nodes. The first two nodes should contain strings and the last 2 nodes should contain numbers (int). I know how to create a linked list with integers as data types, but I don't know how to input strings into the nodes. Can you help me?

  3. hello thank you foe the video its awesome!
    i have a question and its killing me, at 8:32 you're inserting InsertAtHead(2) and InsertAtHead(4) but in your drawing you have '2' in address 400 and '2' in address in 600 did you mean to put 4 ?? or are we replicating the Head with the val 2?

  4. wait , so by the way you insert node, after the second and third insertions,
    the order will actually be " head (which is the third insert node) -> node (from the second insertion) -> node( from the first insertion) "
    Therefore, you are always making the new insert node as the first one in the list but not the last one ?

    Can anyone tell me what is the standard way or most common way to order the double link list when it comes to insertion ?

  5. I did all main functions with proper *head arg in C++.
    Couldn't have done it without this great teacher! Thank you very much!

    #include <iostream>

    #include <new>

    struct Node {

    int data;

    Node* prev;

    Node* next;

    };

    Node* GetNewNode(int data) {

    Node* newNode = new Node();

    newNode->data = data;

    newNode->prev = NULL;

    newNode->next = NULL;

    return newNode;

    }

    Node* InsertStart(Node* headP, int data) {

    Node* newNode = GetNewNode(data);

    if (headP == NULL) {

    headP = newNode;

    } else {

    headP->prev = newNode;

    newNode->next = headP;

    headP = newNode;

    }

    return headP;

    }

    Node* InsertEnd(Node* headP, int data) {

    Node* newNode = GetNewNode(data);

    if (headP == NULL) {

    headP = newNode;

    } else {

    Node* prevNode = headP;

    while (prevNode->next != NULL) {

    prevNode = prevNode->next;

    }

    prevNode->next = newNode;

    newNode->prev = prevNode;

    }

    return headP;

    }

    Node* InsertPos(Node* headP, int data, int pos) {

    Node* newNode = GetNewNode(data);

    if (pos == 1) {

    headP->prev = newNode;

    newNode->next = headP;

    headP = newNode;

    } else {

    Node* prevNode = headP;

    for (int i = 1; i < pos-1; i++) {

    prevNode = prevNode->next;

    }

    newNode->next = prevNode->next;

    newNode->prev = prevNode;

    if (prevNode->next != NULL) prevNode->next->prev = newNode;

    prevNode->next = newNode;

    }

    return headP;

    }

    Node* Delete(Node* headP, int pos) {

    Node* temp = headP;

    if (pos == 1) {

    temp->next->prev = NULL;

    headP = temp->next;

    delete temp;

    } else {

    for (int i = 1; i < pos-1; i++) {

    temp = temp->next;

    }

    Node* currentPos = temp->next;

    temp->next = currentPos->next;

    if (currentPos->next != NULL) currentPos->next->prev = temp;

    delete currentPos;

    }

    return headP;

    }

    Node* Reverse(Node* headP) {

    while (headP->next != NULL) {

    headP = headP->next;

    headP->prev->next = headP->prev->prev;

    headP->prev->prev = headP;

    }

    headP->next = headP->prev;

    headP->prev = NULL;

    return headP;

    }

    void Print(Node* headP) {

    std::cout << "Forward:";

    while (headP != NULL) {

    std::cout << " " << headP->data;

    headP = headP->next;

    }

    std::cout << std::endl;

    }

    void ReversePrint(Node* headP) {

    if (headP == NULL) return;

    while (headP->next != NULL) {

    headP = headP->next;

    }

    std::cout << "Reverse:";

    while (headP != NULL) {

    std::cout << " " << headP->data;

    headP = headP->prev;

    }

    std::cout << std::endl;

    }

    int main() {

    Node* listNumbers = NULL;

    listNumbers = InsertStart(listNumbers, 2);

    listNumbers = InsertStart(listNumbers, 4);

    listNumbers = InsertStart(listNumbers, 8);

    listNumbers = InsertStart(listNumbers, 1);

    Print(listNumbers);

    ReversePrint(listNumbers);

    listNumbers = InsertEnd(listNumbers, 6);

    listNumbers = InsertEnd(listNumbers, 0);

    listNumbers = InsertEnd(listNumbers, 7);

    listNumbers = InsertEnd(listNumbers, 5);

    Print(listNumbers);

    ReversePrint(listNumbers);

    listNumbers = Delete(listNumbers, 3);

    listNumbers = Delete(listNumbers, 5);

    Print(listNumbers);

    ReversePrint(listNumbers);

    listNumbers = Reverse(listNumbers);

    Print(listNumbers);

    ReversePrint(listNumbers);

    listNumbers = InsertPos(listNumbers, 3, 2);

    listNumbers = InsertPos(listNumbers, 9, 8);

    Print(listNumbers);

    ReversePrint(listNumbers);

    return 0;

    }

  6. JAVA CODE – REVERSE PRINT

    public void showReverse() {
    Node pointer = head;
    while (pointer.getNext()!=null) {
    pointer=pointer.getNext();
    }

    while(pointer!=null) {
    System.out.print(pointer.getValue()+"|");
    pointer=pointer.getPrev();
    }
    System.out.println();
    }

  7. JAVA CODE – PRINT

    public void show() {
    Node pointer = head;
    while(pointer!=null) {
    System.out.print(pointer.getValue()+ "|");
    pointer= pointer.getNext();
    }
    System.out.println();
    }

  8. JAVA CODE – INSERT

    public boolean insertItem(int item) {

    System.out.println("Inserting item: "+ item);
    Node newNode = new Node(item);

    if(head==null) {
    head = newNode;
    head.setPrev(null);
    head.setNext(null);
    return true;
    }

    /**Inserting element at the head**/
    /*newNode.setNext(head);
    head.setPrev(newNode);
    newNode.setPrev(null);
    head=newNode;*/

    /**Inserting element at the tail**/
    Node pointer = head;
    while(pointer.getNext()!=null) {
    pointer = pointer.getNext();
    }
    pointer.setNext(newNode);
    newNode.setPrev(pointer);
    newNode.setNext(null);

    return true;
    }

  9. wow sir
    finally i understand why we are using dynamic memory allocation instead of normal allocation
    i know you cant read any of our comments but still i want to say that u will always be the best teacher not only for me but for most of the online community who are still watching and learning from your videos

LEAVE A REPLY

Please enter your comment!
Please enter your name here