An outline of the Class definition of a doubly linked list is given below. Using
ID: 3699430 • Letter: A
Question
An outline of the Class definition of a doubly linked list is given below. Using only the methods given here, write the method
void List<List_entry> :: delete(int )
that deletes an element at position pos in the range 0,1,2,…, count-1. You may assume that the value of pos is valid (i.e. 0<=pos<count) so that there will be no need to return error.
template <class Node_entry>
struct Node {
// data members
Node_entry entry;
Node<Node_entry> *next;
Node<Node_entry> *back;
// constructors
Node();
Node(Node_entry, Node<Node_entry> *link_back = NULL,
Node<Node_entry> *link_next = NULL);
};
typedef Node_entry List_entry
template <class List_entry>
class List {
public:
// add code here
protected:
// Data members
int count; // number of entries in the list
Node<List_entry> *head; // points to the first item of the list
}
Explanation / Answer
Here is the code to delete a node in the specified position in DLL.
* C++ implementation to delete a doubly Linked List node
at the given position */
#include <bits/stdc++.h>
using namespace std;
/* a node of the doubly linked list */
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
/* Function to delete a node in a Doubly Linked List.
head_ref --> pointer to head node pointer.
del --> pointer to node to be deleted. */
void deleteNode(struct Node** head_ref, struct Node* del)
{
/* base case */
if (*head_ref == NULL || del == NULL)
return;
/* If node to be deleted is head node */
if (*head_ref == del)
*head_ref = del->next;
/* Change next only if node to be deleted is NOT
the last node */
if (del->next != NULL)
del->next->prev = del->prev;
/* Change prev only if node to be deleted is NOT
the first node */
if (del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied by del*/
free(del);
}
/* Function to delete the node at the given position
in the doubly linked list */
void deleteNodeAtGivenPos(struct Node** head_ref, int n)
{
/* if list in NULL or invalid position is given */
if (*head_ref == NULL || n <= 0)
return;
struct Node* current = *head_ref;
int i;
/* traverse up to the node at position 'n' from
the beginning */
for (int i = 1; current != NULL && i < n; i++)
current = current->next;
/* if 'n' is greater than the number of nodes
in the doubly linked list */
if (current == NULL)
return;
/* delete the node pointed to by 'current' */
deleteNode(head_ref, current);
}
/* Function to insert a node at the beginning
of the Doubly Linked List */
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;
/* since we are adding at the beginning,
prev is always NULL */
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given doubly
linked list */
void printList(struct Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Create the doubly linked list 10<->8<->4<->2<->5 */
push(&head, 5);
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
cout << "Doubly linked list before deletion:n";
printList(head);
int n = 2;
/* delete node at the given position 'n' */
deleteNodeAtGivenPos(&head, n);
cout << " Doubly linked list after deletion:n";
printList(head);
return 0;
}
Here is the code to delete a node in the specified position in DLL.
* C++ implementation to delete a doubly Linked List node
at the given position */
#include <bits/stdc++.h>
using namespace std;
/* a node of the doubly linked list */
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
/* Function to delete a node in a Doubly Linked List.
head_ref --> pointer to head node pointer.
del --> pointer to node to be deleted. */
void deleteNode(struct Node** head_ref, struct Node* del)
{
/* base case */
if (*head_ref == NULL || del == NULL)
return;
/* If node to be deleted is head node */
if (*head_ref == del)
*head_ref = del->next;
/* Change next only if node to be deleted is NOT
the last node */
if (del->next != NULL)
del->next->prev = del->prev;
/* Change prev only if node to be deleted is NOT
the first node */
if (del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied by del*/
free(del);
}
/* Function to delete the node at the given position
in the doubly linked list */
void deleteNodeAtGivenPos(struct Node** head_ref, int n)
{
/* if list in NULL or invalid position is given */
if (*head_ref == NULL || n <= 0)
return;
struct Node* current = *head_ref;
int i;
/* traverse up to the node at position 'n' from
the beginning */
for (int i = 1; current != NULL && i < n; i++)
current = current->next;
/* if 'n' is greater than the number of nodes
in the doubly linked list */
if (current == NULL)
return;
/* delete the node pointed to by 'current' */
deleteNode(head_ref, current);
}
/* Function to insert a node at the beginning
of the Doubly Linked List */
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;
/* since we are adding at the beginning,
prev is always NULL */
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given doubly
linked list */
void printList(struct Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Create the doubly linked list 10<->8<->4<->2<->5 */
push(&head, 5);
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
cout << "Doubly linked list before deletion:n";
printList(head);
int n = 2;
/* delete node at the given position 'n' */
deleteNodeAtGivenPos(&head, n);
cout << " Doubly linked list after deletion:n";
printList(head);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.