Well, for creating linked lists, i always use 2 pointers: one for beginning and one for the end of the list. Is this OK? Or am i required to have just a single pointer pointing to the beginning of the list and then traverse everytime i need to insert? Are there any rules of any sort that say this is how a Data Structure needs to be implemented?

Here is how i usually create a linked list:

struct List {
	int num;
	struct List *nextNode;

struct List *head = NULL;
struct List *tail = NULL;

struct List* getNode()
	struct List *temp = (struct List *)malloc(sizeof(struct List));
	return temp;

/* Insert into list */
void insertNode(struct List *node, int num)
	struct List *temp;
	temp = getNode();

	if (node == NULL) {		
		temp->num = num;
		temp->nextNode = NULL;
		head = temp;
		tail = temp;
	} else {
		head->nextNode = temp;
		head = temp;
		head->nextNode = NULL;
		head->num = num;
6 Years
Discussion Span
Last Post by Schol-R-LEA

It is expedient for you to have two pointers, a *next and a *back. So that at any given point, you can get access to both the preceding and the conceding nodes.



Well, i was talking about a singly linked list.


It depends on how you're handling the inserts, and whether you're using the list as a queues or not. If you are inserting to the end of the list, then having a pointer to the last element is a practical way of speeding up insertions. However, how you insert may depend on how you are using the list.

If you are using the list as a first-in-first-out queue, then it makes sense to have an end pointer, as you would need rapid access to both ends of the list, and would want to insert to the end.

However, if you're using the list as a stack, it would make more sense to insert to and remove from the top of the list, in which case having an end pointer isn't helpful.

If it is an ordered list, you can use the end pointer to see if an inserted element sorts higher than the current end of the list, in which case you can insert to the end directly; otherwise, you would have to traverse the list to find the insertion point. Whether this optimization is worth the trouble would depend on whether you expect most new elements to come at the end of the list or not.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.