Implementing Linked List Utility Functions. PROGRAM MUST BE IN C PROGRAMMING AND
ID: 3869291 • Letter: I
Question
Implementing Linked List Utility Functions.
PROGRAM MUST BE IN C PROGRAMMING AND PLEASE COMPLETE ALL AS WELL AS SEND SCREENSHOT OF OUTPUT FOR THE THUMBS UP!!
Examine the files list.h and llist.c in the src directory where you found this handout.
You will discover that it is a partially implemented linked list “module”.
The lists store numeric values (the type of which can be changed by altering the typedef for ElemType in list.h).
As in previous projects, the .h file gives the interface for an ADT while the actual implementation is given in the .c file. The members of list_struct are also “hidden” in the .c file. The ADT defines many natural operations on lists -- some of these have already been implemented and will be used as motivating examples during lecture; others have not been implemented: It is your job to do the implementation! Look for TODO labels throughout the files.
A subtle detail: why did I decide to name the header file list.h (one ‘l’), but the implementation file llist.c (two ‘l’s)???
So… part I is completion of all of the TODO items specified.
Rules: you cannot change list.h (except maybe to experiment with different ElemTypes). All of your work is in llist.c (except testing code).
Discussion: The given linked list structure has two “levels”:
At the “lowest” level are the linked-list nodes themselves specified as:
typedef struct node {
ElemType val;
struct node *next;
} NODE;
However, the type NODE isn’t even visible to a client program. Only the type LIST is
visible to a client (just the type -- not the struct members). Through the header file, LIST is equivalent to a struct list_struct which is specified as follows:
struct list_struct {
NODE *front;
NODE *back;
};
Here is a diagram of a list with three entries: <3, 8, 2>. The struct at the left (a LIST) gives access to the actual nodes.
The table on the next pages enumerates the functions to be implemented (identified with “TODO” in both list.h and llist.c) . Table includes a brief description and approximate “difficulty level” on a scale 1-3. See llist.h for detailed specifications.
FUNCTION NAME
SHORT DESCRIPTION
lst_to_array
Returns a dynamically allocated array populated with the elements of a given list
lst_clone
Builds and returns a clone of a given list (a deep copy)
lst_increment_vals
Increments all of the elements in a given list
lst_are_equal
Determines if two given lists are equal (same length and same values in same sequence)
lst_pop_back
Removes last element in list; returns value removed
lst_reverse
Reverses the order of a given list.
Actually changes the list -- doesn’t just print it in reverse order.
lst_sra_bad_case
Builds a list which makes the lst_remove_all_slow function run in quadratic time.
(See .h file for details)
This function has already been written and will be used for demo/discussion in class.
lst_remove_all_fast
Removes all occurrence of given value from given list.
Does operation in “one pass” and takes linear time.
Concept not hard, but attention to detail will pay off!
FUNCTION NAME
SHORT DESCRIPTION
lst_is_sorted
Determines if a given list is in sorted order from smallest to largest.
lst_insert_sorted
Inserts a new element into a list assumed to be sorted. Resulting list sorted (i.e., new element inserted where it belongs)
lst_merge_sorted
Takes two lists assumed to be sorted and merges them into a single sorted list.
After call, the first list (argument) is the merged list and the 2nd list (arg) becomes empty.
Given lists are assumed to be sorted (this property does not need to be separately checked).
No new nodes are allocated (existing nodes are relinked).
How To Get Started
You have been given a Makefile and a skeleton driver/tester program (ll_tst.c). Use them (and feel free to develop separate driver/tester programs) to help perform testing during development.
Overall, you know the drill for this kind of assignment:
Pick a function (start with easier ones)
Implement that function
Write test code for function in ll_tst.c or another driver program
Debug function
Re-test function
Repeat 4, 5 until satisfied
Think of test cases you may have missed
New test cases: Goto 3
No new tests/satisfied: Goto 1
ALL SOURCE CODE IS BELOW HERE SEPERATED BY DASHED LINES!
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
list.h
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
llist.c
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
quad.c
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------MakeFile
llist.o: list.h llist.c
gcc -c llist.c
ll_tst: ll_tst.c llist.o
gcc -o ll_tst ll_tst.c llist.o
quad: quad.c
gcc -o quad quad.c
clean:
rm quad ll_tst llist.o
FUNCTION NAME
SHORT DESCRIPTION
lst_to_array
Returns a dynamically allocated array populated with the elements of a given list
lst_clone
Builds and returns a clone of a given list (a deep copy)
lst_increment_vals
Increments all of the elements in a given list
lst_are_equal
Determines if two given lists are equal (same length and same values in same sequence)
lst_pop_back
Removes last element in list; returns value removed
lst_reverse
Reverses the order of a given list.
Actually changes the list -- doesn’t just print it in reverse order.
lst_sra_bad_case
Builds a list which makes the lst_remove_all_slow function run in quadratic time.
(See .h file for details)
This function has already been written and will be used for demo/discussion in class.
lst_remove_all_fast
Removes all occurrence of given value from given list.
Does operation in “one pass” and takes linear time.
Concept not hard, but attention to detail will pay off!
front val3 val 8 val |2 backExplanation / Answer
Hi this is my version of linked list
/*
* Llist.h
*
* Author: Rj
*/
#ifndef LLIST_H_
#define LLIST_H_
#include <iostream>
#include "RjExceptions.cpp"
template <typename T>
struct Node {
Node<T> *next;
T val;
};
/**
* Creates a singly linked list with a **head** and a **last**. **head** will be
* used to store the address of the first node ever created and the latest will
* be stored in the last.
*/
template <typename T>
class Llist {
// This will store the first node's address.
Node<T> *head;
// This is going to hold the latest node's address.
Node<T> *last;
public:
// CONSTRUCTOR
Llist();
// Adds a val to list.
void add(T val);
// Add object at given index.
void add(int indx, T val);
// Add to start.
void add_front(T val);
// Iterate.
void iterate();
// Reverse iterate.
void iterate_reverse();
// Get the element at index.
T at(int indx);
// Gets the index of certain object.
int indexOf(T val);
// Add object at given index.
void update(int indx, T val);
// Delete
void remove(int indx);
void pop_front();
void pop_back();
};
#endif /* LLIST_H_ */
/*
* Llist.cpp
*
* Author: Rj
*/
#include "Llist.h"
/**
* Constructor function
* This function Initializes head and last to NULL.
*/
template <typename T>
Llist<T>::Llist() : head{ NULL }, last{ NULL }
{};
/**
* Adds a val to the list.
* @param { T } val - val of the object to add.
*/
template <typename T>
void Llist<T>::add(T val) {
// If it is the first node
// Just normal initializing does not produce new objects every time the method is
// called.
Node<T> *nd1 = new Node<T>;
nd1->next = NULL;
if (head == NULL) {
head = nd1;
}
else {
last->next = nd1;
}
nd1->val = val;
last = nd1;
};
/**
* @Overload
* Add given object at a given index.
* @param { int } indx - Index to append at.
* @param { T } val - Object to append.
*/
template <typename T>
void Llist<T>::add(int indx, T val) {
Node<T> *temp1{ head };
Node<T> *temp2{ NULL };
int i{ 0 };
do {
if (i == indx && i != 0) {
Node<T> *nd1 = new Node<T>;
// Copy Previous one's.
nd1->next = temp1;
nd1->val = val;
temp2->next = nd1;
}
++i;
temp2 = temp1;
temp1 = temp1->next;
} while(temp1 != NULL);
}
/**
* Iterates over the list from start to end and prints to the screen.
*/
template <typename T>
void Llist<T>::iterate() {
if (head == NULL) {
list_un_inited err;
throw err;
}
// Iterate through the list until you hit a NULL.
Node<T> *temp{ head };
do {
std::cout << temp->val << std::endl;
temp = temp->next;
} while(temp != NULL);
};
/**
* Returns the object at the given index.
* @param { int } indx - Index of the object to get.
*/
template <typename T>
T Llist<T>::at(int indx) {
Node<T> *temp{ head };
int i{ 0 };
do {
if (i == indx) {
return temp->val;
}
++i;
temp = temp->next;
} while(temp != NULL);
out_of_bounds_index err;
throw err;
}
template <typename T>
int Llist<T>::indexOf(T val)
{
Node<T> *temp{ head };
int i{ 0 };
do {
if (temp->val == val) {
return i;
}
++i;
temp = temp->next;
} while(temp != NULL);
out_of_bounds_index err;
throw err;
}
/**
* Adds an object to the start of an array.
* @param { T } val - Object to add.
*/
template <typename T>
void Llist<T>::add_front(T val) {
// Create a new node.
Node<T> *nd1 = new Node<T>;
// Set its prev to NULL.
nd1->next = head;
nd1->val = val;
// Change others
head = nd1;
};
/**
* Adds an object to the start of an array.
* @param { int } indx - Index of object to change.
* @param { T } val - Object to change index to.
*/
template <typename T>
void Llist<T>::update(int indx, T val) {
Node<T> *temp{ head };
int i{ 0 };
do {
if (i == indx) {
temp->val = val;
}
++i;
temp = temp->next;
} while(temp != NULL);
};
/**
* Deletes an object at given index
* @param { int } indx - Index of object to remove.
*/
template <typename T>
void Llist<T>::remove(int indx) {
Node<T> *temp1{ head };
Node<T> *temp2{ NULL };
int i{ 0 };
do {
if (i != 0 && i == indx) {
temp2->next = temp1->next;
}
++i;
temp2 = temp1;
temp1 = temp1->next;
} while(temp1 != NULL);
temp2->next = NULL;
};
/**
* Deletes the first element of the array.
*/
template <typename T>
void Llist<T>::pop_front() {
head = head->next;
};
/**
* Deletes the last element of an array.
*/
template <typename T>
void Llist<T>::pop_back() {
Node<T> *temp1{ head };
Node<T> *temp2{ NULL };
do {
temp2 = temp1;
temp1 = temp1->next;
} while(temp1->next != NULL);
temp2->next = NULL;
};
//============================================================================
// Name : SinglyLinkedListDriver.cpp
// Author : Ramachandra jr
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include "Llist.cpp"
#include <cstdlib>
int main() {
srand(time(NULL));
Llist<int> mylist1{};
const int MAX_NUM = 100;
for (int i = 0; i < 20; ++i) {
int randnum = (rand()%MAX_NUM)+1;
mylist1.add(randnum);
}
mylist1.iterate();
return 0;
}