Homework SourseData Structures in C I am really new to C so links are reall
Data Structures in C++
I am really new to C++, so links are really hard topic for me. It would be nice if you can provide explanations of what doubly linked lists are and of some of you steps... Thank you
In this assignment, you will implement a doubly-linked list class, together with some list operations. To make things easier, you’ll implement a list of int, rather than a template class.
Solution
A variable helps us to identify the data. For ex: int a = 5; Here 5 is identified through variable a.
Now, if we have collection of integers, we need some representation to identify them. We call it array. For ex: int arr[5]
This array is nothing but a Data Structure.
So, a Data Structure is a way to group the data.
There are many Data Structures available like Arrays, Linked List, Doubly-Linked list, Stack, Queue, etc.
Doubly-Linked list are the ones where you can traverse from the current node both in left and right directions.
Why so many different types of Data Structures are required ?
Answer is very simple, grouping of data, storage of data and accessing the data is different.
For example, in case of Arrays we store all the data in contiguous locations.
What if we are not able to store the data in contiguous locations because we have huge data. Answer is go for Linked List/Doubly-Linked list.
Here we can store the data anywhere and link the data through pointers.
I will try to provide comments for the code you have given. May be this can help you.
#pragma once
/*
dlist.h
Doubly-linked lists of ints
*/
#include <ostream>
class dlist {
public:
dlist() { }
// Here we are creating a NODE, it has a integer value and two pointers.
// One pointer is to move to next node and other to go back to previous node.
struct node {
int value;
node* next;
node* prev;
};
// To return head pointer, i.e. start of the Doubly-Linked list.
node* head() const { return _head; }
// To return Tail pointer, i.e. end of the Doubly-Linked list.
node* tail() const { return _tail; }
// **** Implement ALL the following methods ****
// Returns the node at a particular index (0 is the head).
node* at(int index){
int cnt = 0;
struct node* tmp = head();
while(tmp!=NULL)
{
if (cnt+1 == index)
return tmp;
tmp = tmp->next;
}
}
// Insert a new value, after an existing one
void insert(node *previous, int value){
// check if the given previous is NULL
if (previous == NULL)
{
printf(\"the given previous node cannot be NULL\");
return;
}
// allocate new node
struct node* new_node =(struct node*) malloc(sizeof(struct node));
// put in the data
new_node->data = new_data;
// Make next of new node as next of previous
new_node->next = previous->next;
// Make the next of previous as new_node
previous->next = new_node;
// Make previous as previous of new_node
new_node->prev = previous;
// Change previous of new_node\'s next node
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
// Delete the given node
void del(node* which){
struct node* head_ref = head();
/* base case */
if(*head_ref == NULL || which == NULL)
return;
/* If node to be deleted is head node */
if(*head_ref == which)
*head_ref = which->next;
/* Change next only if node to be deleted is NOT the last node */
if(which->next != NULL)
which->next->prev = which->prev;
/* Change prev only if node to be deleted is NOT the first node */
if(which->prev != NULL)
which->prev->next = which->next;
/* Finally, free the memory occupied by which*/
free(which);
return;
}
// Add a new element to the *end* of the list
void push_back(int value){
// allocate node
struct node* new_node = (struct node*) malloc(sizeof(struct node));
struct node* head_ref = head();
struct node *last = *head_ref;
// put in the data
new_node->data = value;
// This new node is going to be the last node, so make next of it as NULL
new_node->next = NULL;
// If the Linked List is empty, then make the new node as head
if (*head_ref == NULL)
{
new_node->prev = NULL;
*head_ref = new_node;
return;
}
// Else traverse till the last node.
while (last->next != NULL)
last = last->next;
// Change the next of last node
last->next = new_node;
// Make last node as previous of new node
new_node->prev = last;
return;
}
// Add a new element to the *beginning* of the list
void push_front(int value){
//allocate node
struct node* new_node = (struct node*) malloc(sizeof(struct node));
//put in the data
new_node->data = value;
// Make next of new node as head and previous as NULL
struct node* head_ref = head();
new_node->next = (*head_ref);
new_node->prev = NULL;
//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;
}
// Remove the first element
void pop_front(){
struct node *toDelete;
struct node *head = head();
if(head == NULL)
{
printf(\"Unable to delete. List is empty.\ \");
}
else
{
toDelete = head;
head = head->next; //Move head pointer to 2 node
head->prev = NULL; //Remove the link to previous node
free(toDelete); //Delete the first node from memory
printf(\"SUCCESSFULLY DELETED NODE FROM BEGINNING OF THE LIST.\ \");
}
}
// Remove the last element
void pop_back(){
struct node * toDelete;
struct node *last = head();
while(last.next!=NULL)
{
last = last->next;
}
if(last == NULL)
{
printf(\"Unable to delete. List is empty.\ \");
}
else
{
toDelete = last;
last = last->prev; //Move last pointer to 2nd last node
last->next = NULL; //Remove link to of 2nd last node with last node
free(toDelete); //Delete the last node
printf(\"SUCCESSFULLY DELETED NODE FROM END OF THE LIST.\ \");
}
}
// Get the size of the list
int size(){
int cnt = 0;
struct node* head_ref = head();
while(head_ref!=NULL)
{
cnt++;
head_ref = head_ref->next;
}
return cnt;
}
// Returns true if the list is empty
bool empty(){
struct node* head_ref = head();
if(head_ref == NULL)
return true;
else
return false;
}
private:
node* _head = nullptr;
node* _tail = nullptr;
};
// **** Implement ALL the following functions ****
/* out << l
Prints a list to the ostream out. This is mostly for your convenience in
testing your code; it\'s much easier to figure out what\'s going on if you
can easily print out lists!
*/
std::ostream& operator<< (std::ostream& out, dlist& l);
/* a == b
Compares two lists for equality, returning true if they have the same
elements in the same positions. (Hint: it is *not* enough to just compare
pointers! You have to compare the values stored in the nodes.)
*/
bool operator== (dlist& a, dlist& b);
/* a + b
Returns a new list consisting of all the elements of a, followed by all the
elements of b (i.e., the list concatenation).
*/
dlist operator+ (dlist& a, dlist& b);
/* reverse(l)
Returns a new list that is the *reversal* of l; that is, a new list
containing the same elements as l but in the reverse order.
*/
dlist reverse(dlist& l);
