Question

C++ Goals  Build single linked lists using pointers  Learn how to manipulate linked lists...

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

Homework Answers

Answer #1

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

}

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
How do you delete the tail node of a singly linked list if the link has...
How do you delete the tail node of a singly linked list if the link has the head and does not have tail? Write the code. How much time does it take to Do it?
How do you delete the tail node of a singly linked list if the link has...
How do you delete the tail node of a singly linked list if the link has the head and does no have tail? Write the code. How much time does it take to do it? (java)
i want to complete this code to insert a new node in the middle of list...
i want to complete this code to insert a new node in the middle of list (take a node data from user, search the node and insert new node after this node). this is the code #include <iostream> #include <stdlib.h> using namespace std ; struct Node{                int data;                Node *link ;}; struct Node *head=NULL, *tail=NULL; /* pointers to Node*/ void InsertFront(); void InsertRear(); void DeleteFront(); void DeleteRear(); int main(){                int choice;                do{                               cout << "1:...
In this code, I build a single-linked list using a node class that has been created....
In this code, I build a single-linked list using a node class that has been created. How could I change this code to take data of type T, rather than int. (PS: ignore the fact that IOHelper.getInt won't work for the type T... ie second half of main). Here's my code right now: public class SLList { public SLNode head = null; public SLNode tail = null; public void add(int a) {// add() method present for testing purposes SLNode newNode...
The main goal is to implement two recursive methods, each is built to manipulate linked data...
The main goal is to implement two recursive methods, each is built to manipulate linked data structures. To host these methods you also have to define two utterly simplified node classes. 1.) Add a class named BinaryNode to the project. This class supports the linked representation of binary trees. However, for the BinaryNode class Generic implementation not needed, the nodes will store integer values The standard methods will not be needed in this exercise except the constructor 2.) Add a...
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete....
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete. Return true or false to indicate success or failure. Delete the memory the node was using The algorithm for deleting a Node to a Linked List (general case): ● Begin at the head. ● Compare the id to the current node. ● If search id > current id, stop. ● Detach the current Node ○ current->previous->next = current->next ○ current->next->previous = current->previous ● Deallocate...
Data Structure in C++ I keep getting the same warning, and I cant seem to fix...
Data Structure in C++ I keep getting the same warning, and I cant seem to fix it.. Can you explain to me what I am doing wrong? Warning: dlist.cc: In function 'std::ostream& operator<<(std::ostream&, dlist&)': dlist.cc:66:10: error: invalid initialization of reference of type 'std::ostream& {aka std::basic_ostream&}' from expression of type 'dlist::node*' dlist.cc: In function 'dlist operator+(dlist&, dlist&)': dlist.cc:93:8: error: invalid operands of types 'dlist::node*' and 'dlist::node*' to binary 'operator+' dlist.cc:97:8: error: could not convert 'result' from 'int' to 'dlist' My code:...
It is about C++linked list code. my assignment is making 1 function, in below circumstance,(some functions...
It is about C++linked list code. my assignment is making 1 function, in below circumstance,(some functions are suggested for easier procedure of making function.) void search_node(struct linked_list* list, int find_node_ value) (The function to make) This function finds the node from the list that value is same with find_node_value and count the order of the node. This function should print message “The order of (node_value) is (order).” and error message “Function search_node : There is no such node to search.”....
C PROGRAMMING Doubly Linked List For this program you’ll implement a doubly linked list of strings....
C PROGRAMMING Doubly Linked List For this program you’ll implement a doubly linked list of strings. You must base your code on the doubly linked list implementation given in my Week 8 slides. Change the code so that instead of an ‘int’ each node stores a string (choose a suitable size). Each node should also have a next node pointer, and previous node pointer. Then write functions to implement the following linked list operations: • A printList function that prints...
A Queue is a linked list with pointers to both the head of the list as...
A Queue is a linked list with pointers to both the head of the list as well as the tail (or the last element) of the list. Given a queue Q, Q.head gives the head of the queue and Q.tail gives the tail of the queue. Give O(1) time algorithms for the following tasks. Enqueue • Input: A queue Q of distinct integers and a queue element a not in Q. 1 • Output: Q with the element a added...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT