Embedded Files
A few students encounter challenges in handling the pointers in linked list. In this page, I will try to explain three different ways I used to load a stock file into a doubly-linked list. The first routine insert_front() just stick the node at the beginning of the list. The other two insert_inorder() and insert_inorder2pt() insert the node in "proper order" such that the result is a sorted link 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 (length == 0) {
p->prev = p->next = NULL;
head = tail = p;
length++;
return;
}
p->next = head;
p->prev = NULL;
p->next->prev = p;
head = p;
length++;
}
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
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 (length == 0) {
p->prev = p->next = NULL;
head = tail = p;
length++;
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
p->next = temp; //fwd link
if (head==temp) head = p; else temp->prev->next = p; // first node case
p->prev = temp->prev; temp->prev = p; //bkwd link
length++;
return;
}
}
// nobody is larger, insert at end
p->next = NULL; p->prev = tail;
tail->next = p; tail = p; length++;
}
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 (length == 0) {
p->prev = p->next = NULL;
head = tail = p;
length++;
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
p->prev = current->prev; current->prev = p; //bkwd link
length++;
return;
}
}
// nobody is larger, insert at end
p->next = NULL; p->prev = tail;
tail->next = p; tail = p; length++;
}
Discussions
I am sure there are many different solutions to this question. My intent is to provide you something that you can get on with your own experiments.
Having length in this particular situation is not really useful. In fact, without it may make it cleaner.
Doubly-linked list actually complicated things too. It would be a good exercise to do one for forward linked list. It would be likely that two pointers approach will be easier.
Page updated
Google Sites
Report abuse