# Doubly Linked List – Implementation in C/C++

31
18

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:

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

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);

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. please do make more videos on linked list various operations like swapping alternate nodes..!!!

5. 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 ?

6. 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);

} else {

}

}

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

Node* newNode = GetNewNode(data);

} else {

while (prevNode->next != NULL) {

prevNode = prevNode->next;

}

prevNode->next = newNode;

newNode->prev = prevNode;

}

}

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

Node* newNode = GetNewNode(data);

if (pos == 1) {

} else {

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;

}

}

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

if (pos == 1) {

temp->next->prev = NULL;

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;

}

}

}

}

std::cout << "Forward:";

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

}

std::cout << std::endl;

}

}

std::cout << "Reverse:";

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

}

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;

}

7. JAVA CODE – REVERSE PRINT

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

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

8. JAVA CODE – PRINT

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

9. JAVA CODE – INSERT

public boolean insertItem(int item) {

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

return true;
}

newNode.setPrev(null);

/**Inserting element at the tail**/