#ifndef LINKEDLIST_H
#define LINKEDLIST_H
//******************************************************************
// SPECIFICATION FILE (linkedlist.h)
// This file gives the specification of a dynamic linked list representation of
// a linked list.
// The list nodes are maintained in ascending order of value
// The private data members:
// head pointer to the first node in the list
// if the list is empty, node is set to NULL
// currentsize the number of integers currently in the list
//******************************************************************
struct node { // structure of node of list
int item; // integer in the list
node* link; // link to next node in list
};
class linkedlist
{
public:
linkedlist(); //Constructor
// Precondition
// Postcondition
// List is empty, head is set to NULL
void Print();
// Postcondition:
// All node values (if any) in list have been printed
void Insert( /* in */ int item );
// Precondition:
// item is value to add to list
// Postcondition:
// item is in list
// && List nodes are in ascending order
void Delete( /* in */ int item );
// Precondition:
// item is value to delete from list
// Postcondition:
// item deleted from the list
// && List nodes are in ascending order
int linkedlist::Size();
// Postcondition:
// number of nodes (items) in the list is returned
linkedlist::~linkedlist(); // Destructor
// Precondition:
// Link list created by constructor
// (may be empty)
// Postcondition:
// Storage for any nodes on the list freed
private:
int currentsize; // current number of items in list
node* head; // start of linked list
};
#endif
//implementation for the linkedlist.h class
#include<iostream>
usingnamespace std;
#include"linkedlist.h"
linkedlist::linkedlist() // constructor
{
// Initialize object private data
}
void linkedlist::Print()
{
// Initialize a pointer to first node in list
// head is first node in list (NULL if list empty)
// while items in the list
while () {
// print the item
// go to next item in the list
}
cout << endl;
}
void linkedlist::Insert(int item)
{
// initialize a current pointer to the head
// initialize a previous pointer to NULL
// Find where to put item. We need to put item between previous
// and current pointers in list
// Search list until list empty or found higher item
while()
{
// previous points to last node checked
// current goes forward in list
}
// increment list size - always room for a new node in dynamic linked list
// allocate a new node
// if insertion in empty list or before first item
if()
{
// This node before first item
// new item (data) for allocated node
// now start of list - point to it
}
else { // else insert into list or at end
// new item (data) for allocated node
// this new node points to current
// previous node points to new node
}
}
void linkedlist::Delete(int item)
{
// Allocate current pointer initialize to head
// Allocate a previous pointer initialized to NULL
// while items in list and item not found
// to speed search stop if item > current item (ordered list)
while() {
// previous is last item checked
// current is next to check
}
// If found (must check current !=NULL in case item > last item in list)
if(){
// one less node in list
// if deleting first node in list
if()
{
// head now first node remaining
}
else { // deleting node in list after first one
// skip deleted node in chain
}
// free node storage
}
}
int linkedlist::Size() {
// return current number of nodes
}
linkedlist::~linkedlist() { // Destructor
// start with head
// while nodes in list delete it
while () {
// save next node to delete
// delete this node
// point to saved next node
}
}
As you can tell, the second one is a skeleton. Can someone help me to understand what those comments mean? I get they are telling me what needs to be done but I don't know how to code them at all.
No I would just like further input on what the comments are saying. I'm not very good with the pointers and links so I'm not understanding what they are saying. However, I do have the constructor figured out, along with a few parts of Insert;
linkedlist::linkedlist() // constructor
{
// Initialize object private data
head = NULL;
currentsize = 0;
}
void linkedlist::Insert(int item)
{
// initialize a current pointer to the head
node* location;
location = new node;
// initialize a previous pointer to NULL
node* currPtr = head;
node* prevPtr = NULL;
Only now I don't know what to do with the new pointer
Actually in the private class members you need to add another pointer to node, which will point to the current item of the list...
What you're doing in the insert function is wrong, you dont need to declare all that variables, you only need to alocate a new node, and then assign it's reference to the private class member pointers, the head will point to the beginning of the list, the current will point to the current item of the list...
Quick Eg:
1 2 3 4 5 6
...
private:
int currentsize;
node* head;
node* curr;
...
The insert function will look something like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
void linkedlist::Insert(int item)
{
if(head == 0) //If head points to nothing it means that there is no list yet
{
head = new node; //alocate a new node and return it's reference to head
curr = head; //Ok, current item is for now the first item on the list which the head points to
curr->link = 0; // The next item on the list points to nothing yet...
curr->item = item; // and then we assign the param value to the current item of the list...
}
else // The head points to a node which means that there is at least one node...
{
curr->link = new node; // allocate the next node of the list, linked to current node
curr = curr->link; //ok, now the current item is the new created node
curr->link = 0; // The same as before, the next node points to nothing, which means the end of the list...
curr->item = item; // assign the value...
}
}
