Embedded Files
Follow previous doubly-linked list insertion, I will try forward linked list insertion without length. Hopefully, you will get a better view of tradeoffs. I'll mark the removal and/or changes from the doubly-linked list.
The stockDB.h is show below along side with the load routine. The stock object is the same as discussed in the object design example.
bool stockDB::load(string fn)
{
ifstream fin;
fin.open(fn.c_str());
if (fin.fail()) return(false);
while(!fin.eof()){
stockNode *sp = new stockNode();
fin >> *sp;
insert_front(sp); // try all 3 insertions
insert_inorder(sp); // try all 3 insertions
insert_inorder2pt(sp); // try all 3 insertions
}
fin.close();
return(true);
}
class stockDB
{
public:
stockDB();
bool load(string);
void print();
void print_rev();
void insert_front(stockNode *);
void insert_inorder(stockNode *);
void insert_inorder2pt(stockNode *);
private:
stockNode * head;
// stockNode * tail;
// int length; // try with & without the length member
};
insert_front
void stockDB::insert_front(stockNode *p) // insert front
{
if (head== NULL) {
p->next = NULL;
head = p;
return;
}
p->next = head; // non-empty list, insert front
head = p;
}
Insert_front is the simplest of the three. The first part takes care of the single node case. The rest handles the general non-empty case. Note that there is no ordering sequence on the list.
insert_inorder (see red note)
In order to have a sorted list, we need to define the meaning of order. Here, I simply define it as the order of symbol. The following one line operator overloading routine in stock class provides the comparison function.
bool stock::operator< (const stock& rhs) {
return (symbol < rhs.symbol);
}
To insert into a linked list, we need to consider a few cases:
list is empty
insert at the end
insert at the very beginning and the list is not empty
insert in the middle
Note that the code below is color coded to correspond the cases above. The #3 case is the hardest to debug if you do not consider it in your design. In my opinion, the key to debug the code is to have a good "view" of the list you just built. Then, you can break on every input node, before and after the insertion.
void stockDB::insert_inorder(stockNode *p)
{
if (head==NULL) {
p->next = NULL;
head = p;
return;
}
// find a larger node and insert before it
stockNode * temp = head;
while (temp != NULL) {
if (*temp < *p) temp = temp->next;
else {
// insert before temp
// NOTE: without backward link, we can not find the previous node..... So, this approach is not good. We need to do the two pointers solution described next.
}
insert_inorder2pt
Since many textbook references use two pointers (current and behind) to perform the link list insertion, I tried one by modifying the previous code. It is indeed very similar.
void stockDB::insert_inorder2pt(stockNode *p)
{
if (head == NULL) {
p->next = NULL;
head = p;
return;
}
// find a larger node and insert before it
stockNode *current=head, *behind=NULL;
while (current != NULL) {
if (*current < *p) {
behind = current; current = current->next;
}
else {
// insert before current
p->next = current; //fwd link
if (behind==NULL) head = p; else behind->next = p; // first node case
return;
}
}
// nobody is larger, insert at end
p->next = NULL;
behind->next = p;
}
Page updated
Google Sites
Report abuse