create a linked list

Creating a linked list (either Forward List or Doubly Linked List) can be accomplished in a few different ways. The basic idea is to create an empty list initially and then "insert" as many nodes as needed. In our example below, we will just do insert at the front.

The node definition can be as simple as

class node

{

public:

node* next;

node *prev;

int x; // any object here, int, studentGrade, stock, car, etc

};

Note that we will not use prev in the forward list. It is here for doubly-linked list usage. Other means of creating a node are described in another page. Highly recommend that you understand that topic before this.

create forward list

Technically speaking, a forward list only needs a head pointer. It is created in node *headFwdList=NULL; The rest of the code is doing insert at front. Of course, if the requirement is to insert at the back, then a tail pointer would be quite useful.

// creating forward list

node *headFwdList=NULL;

for (int i = 0; i < 6; i++)

{

node *newNode = new node;

newNode->x = i+1;

newNode->next = headFwdList; // inserting at front

headFwdList = newNode;

}

create doubly linked list

Doubly linked list needs both head and tail pointers. The rest of the code is doing insert at front. If we want "insert at back", or "insert in order" (as in creating ordered list), then the insertion function shall be modified accordingly.

// creating doubly-linked-list

node *headDoublyList=NULL;

node *tailDoublyList=NULL;

for (int i = 0; i < 6; i++)

{

node *newNode = new node;

newNode->x = 2*(i+1); // just dummy content

newNode->prev = NULL; // inserting at front

newNode->next = headDoublyList;

if (headDoublyList != NULL) headDoublyList->prev = newNode; // connect backward pointer, correction made by Stan Lao

headDoublyList = newNode;

if (tailDoublyList==NULL) tailDoublyList=newNode;

}

Better approach to creating a list is to write "insert" and "create" routines separately. That will be left for your exercises.

Discussions

1. My favorite way of creating a link list is to read from a file. We did couple "import" examples in storing object pages earlier . Storing object lists in a disk file could easily be a very simple looping exercise, since object input / output operators are already implemented in the base object class.

2. In previous semester, I use studentgrade file for programming exam. The write-up under sgdb forward linked list implementation is another example of reading objects from file. If you're there, checkout the difference when has-a is used instead of is-a.