Creating Linked Lists

[myk45]

Hello.

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;
	}
}

[roottybrian]

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.

[myk45]

@roottybrian

Well, i was talking about a singly linked list.

[sree_ec]

@roottybrian

Well, i was talking about a singly linked list.

this could be a good read

[Schol-R-LEA]

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.