C++
Goals
Build single linked lists using pointers
Learn how to manipulate linked lists
In this lab, you will create simple single linked structures consisting of Node objects. Each node will have a pointer to the next node. You will use a head pointer to keep track of the first node in the linked list, and a tail pointer to keep track of the last node in the linked list. Set both head and tail to NULL when the list is empty.
All of the code manipulating the linked list should be in the main function. For this lab, you will not implement the linked list operations using functions/methods. The idea is to focus on the low-level manipulation of the links that connect the nodes in the list.
1. Create the linked list: store integer values entered by the user in the linked list. Each node in the list should store one value. Use a menu to get user input values. After the user has entered the sequence of values, the program should print the values in order. Think about how to traverse the list in order to print the values. Meanwhile, you need to set the head and tail pointers to point to the first and last node in the list.
2. Get the head or tail node value: print the values of head or tail node in screen. If the list is empty, print a note as “List is empty!!”
3. Delete the head or tail value: ask the user whether to delete the node in the head or tail of the list. When user chooses one, delete that node by manipulate pointers and print the new head/tail node value. If the list is already empty, print a note like “Deleting failed, list is empty!!” Remember to free the memory after deleting.
Finally, give users options to exit the program or do it again.
Example running:
Welcome to my linked list!
Enter a number: 100
Do you want another num(y or n): y
Enter a number: 30
Do you want another num(y or n): y
Enter a number: 50
Do you want another num(y or n): y
Enter a number: 10
Do you want another num(y or n): n
Your linked list is: 100 30 50 10
Do you want to do get head or tail node value (h or t): t
Tail node is: 10
Do you want to delete head or tail node (h or t): h
The new head node is 30!
Do you want to do this again (y or n)? n
#define SLIST_H;
#include <stdlib.h>
#include <slist.h>
struct snode {
void * data;
struct snode * next;
};
typedef struct snode snode;
struct slist {
snode * head;
snode * tail;
unsigned int count;
};
typedef struct slist slist;
typedef void (*slist_forfn)(void *);
slist * slist_create(void);
void slist_empty(slist * list);
void slist_delete(slist * list);
void slist_add_tail(slist * list, void * data);
void slist_add_head(slist * list, void * data);
void * slist_remove_head(slist * list);
void * slist_delete_tail(slist * list);
void * slist_delete(slist *list, snode *node, snode *previous);
static snode * snode_create(void * data)
{
snode * node = malloc(sizeof(snode));
if (node) {
node->data = data;
node->next = NULL;
}
return node;
}
slist * slist_create(void)
{
slist * list = malloc(sizeof(slist));
if (list) {
list->head = NULL;
list->tail = NULL;
list->count = 0;
}
return list;
}
void slist_empty(slist * list)
{
snode * node, * temp;
node = list->head;
while (node != NULL) {
temp = node->next;
free(node);
node = temp;
}
}
void slist_delete(slist * list)
{
if (list) {
slist_empty(list);
free(list);
}
}
void slist_add_tail(slist * list, void * data)
{
snode * node = snode_create(data);
if (list->head == NULL) {
/* Adding the first node */
list->head = node;
list->tail = node;
}
else {
list->tail->next = node;
list->tail = node;
}
list->count++;
}
void slist_add_head(slist * list, void * data)
{
snode * node = snode_create(data);
if (list->tail == NULL) {
/* Adding the first node */
list->head = node;
list->tail = node;
}
else {
node->next = list->head;
list->head = node;
}
list->count++;
}
void * slist_remove_head(slist * list)
{
void *data = NULL;
if (list->head) {
snode *temp = list->head;
if (list->head->next) {
list->head = list->head->next;
}
else {
/* List is now empty */
list->head = NULL;
list->tail = NULL;
}
data = temp->data;
free(temp);
list->count--;
if (list->count == 1) {
list->tail = list->head;
}
}
return data;
}
void * slist_remove_tail(slist * list)
{
void *data = NULL;
if (list->tail) {
snode *current, *previous = NULL;
current = list->head;
while (current->next) {
previous = current;
current = current->next;
}
data = current->data;
free(current);
if (previous) {
previous->next = NULL;
}
else {
/* List is now empty */
list->head = NULL;
list->tail = NULL;
}
list->count--;
if (list->count == 1) {
list->head = list->tail;
}
}
return data;
}
void * slist_remove(slist *list, snode *node, snode *previous)
{
void *data;
if (node == list->head) {
data = slist_remove_head(list);
}
else {
previous->next = node->next;
data = node->data;
list->count--;
if (list->count == 1) {
list->tail = list->head;
}
else if (node == list->tail) {
list->tail = previous;
}
free(node);
}
return data;
int main(void)
{
slist * list = slist_create();
char * elements[] = {"A", "B", "C", "D", "E", "F"};
const unsigned int n = sizeof(elements) / sizeof(const char*);
unsigned int i;
snode * node, * previous = NULL;
unsigned int found = 0;
/* Populate the list with A, B, ..., F */
for (i = 0; i < n; i++) {
slist_add_tail(list, elements[i]);
}
/* Insert X and Y either side of C */
for (node = list->head; node != NULL && !found; node = node->next) {
if (strcmp((const char*)node->data, "C") == 0) {
slist_insert_before(list, node, previous, "X");
slist_insert_after(list, node, "Y");
found = 1;
}
previous = node;
}
/* Forward iteration */
for (node = list->head; node != NULL; node = node->next) {
printf("%s\n", (const char*)node->data);
}
slist_delete(list);
return 0;
}
Get Answers For Free
Most questions answered within 1 hours.