#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    16
    Rep Power
    0

    Linked List help!


    If anyone could help me, that would be great. We just went over classes and things recently and our teacher didn't really cover things very well.

    This is the assignment:
    /* **********************************************
    Below is the code for an implementation of a linked list. The implementation has one missing method and one flaw.

    Implement the missing size() method, which returns the length of the list.

    Then, fix the insertAt() method so that it does not crash when first is NULL (when all items have been removed from the list).
    ********************************************** */

    Here is the different code files: ( I will separate them with "*")

    **********************************************
    Main:

    Code:
    #include <iostream>
    using namespace std;
    
    #include "linkedlist.hpp"
    
    int main ()
    {
    	LinkedList *list = new LinkedList(3);
    	
    	// Append the values 8, 12, and 2
    	list->insertAt(8, 1);
    	list->insertAt(12, 2);
    	list->insertAt(2, 3);
    	
    	// Print the list
    	for (int i = 0; i < 4; i++) {
    		cout << list->at(i) << " ";
    	}
    	cout << endl;
    	
    	list->removeAt(0);
    	list->removeAt(0);
    	list->removeAt(0);
    	list->removeAt(0);
    	
    	list->insertAt(50, 0);
    	
    	// Print the list
    	cout << list->at(0) << endl;
    	
    	cout << endl;
    	
    	// Free the list
    	delete list;
    }
    **********************************************

    linkedList.hpp

    Code:
    #pragma once
    
    struct ListNode
    {
    	int value;
    	ListNode *next;
    };
    
    // Singly linked list of integers
    class LinkedList
    {
    public:
    	LinkedList (int value);
    	~LinkedList ();
    	
    	int& at (int index);
    	
    	void insertAt (int value, int index);
    	void removeAt (int index);
    	
    	int size ();
    	
    private:
    	ListNode *first;
    };
    **********************************************

    linkedList.cpp

    Code:
    #include <cstddef>
    #include <iostream>
    using namespace std;
    
    #include "linkedlist.hpp"
    
    LinkedList::LinkedList(int initialValue)
    {
    	first = new ListNode;
    	first->value = initialValue;
    	first->next = NULL;
    }
    
    LinkedList::~LinkedList ()
    {
    	ListNode *node = first;
    	
    	while (node != NULL) {
    		ListNode *nodeToDelete = node;
    		node = node->next;
    		delete nodeToDelete;
    	}
    }
    
    int& LinkedList::at (int index) {
    	// Find the node with the given index
    	ListNode *searchNode = first;
    	for (int i = 0; i < index; i++) {
    		searchNode = searchNode->next;
    	}
    	
    	// Return a reference to the value for that node
    	return searchNode->value;
    }
    
    void LinkedList::insertAt (int value, int index)
    {
    	ListNode *node = new ListNode;
    	node->value = value;
    	
    	if (index == 0) {
    		// Replace first
    		node->next = first->next;
    		first = node;
    	}
    	else {
    		// Find the node immediately before and insert after it
    		ListNode *searchNode = first;
    		for (int i = 0; i < index - 1; i++) {
    			searchNode = searchNode->next;
    		}
    		
    		node->next = searchNode->next;
    		searchNode->next = node;
    	}
    }
    
    void LinkedList::removeAt (int index)
    {
    	if (index == 0) {
    		// Remove first 
    		ListNode *newFirst = first->next;
    		delete first;
    		first = newFirst;
    	}
    	else {
    		// Find the node immediately before and delete after it
    		ListNode *searchNode = first;
    		for (int i = 0; i < index - 1; i++) {
    			searchNode = searchNode->next;
    		}
    		
    		ListNode *newNext = searchNode->next->next;
    		delete searchNode->next;
    		searchNode->next = newNext;
    	}
    }
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    149
    Rep Power
    36
    And what is your question? Don't just dump your homework here and expect someone to do it for you. We got better **** to do.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    16
    Rep Power
    0
    I didn't ask, "hey could someone do all this for me?" I asked if someone could help me. Meaning, could someone point me in the right direction as to what to do.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    886
    ...I asked if someone could help me. Meaning, could someone point me in the right direction as to what to do.
    Yup, that we can do...

    First read the sticky threads at the top of this forum. Then start doing some of your homework and when you have specific problems, ask specific questions, we'd love to help. Your original post never asked any questions.

    For instance, what part of you assignment do you not understand? If you take a stab at telling us what you think the size() method should do or why insertAt() method is broken, we just might have more motivation to lend you a hand.

    Comments on this post

    • salem agrees : Much better than the reply I wrote, then deleted before posting it :)
    I no longer wish to be associated with this site.

IMN logo majestic logo threadwatch logo seochat tools logo