Member Avatar for 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;
	}
}
  • 4 Contributors
  • 4 Replies
  • 135 Views
  • 14 Hours Discussion Span
  • Latest Post Latest Post by Schol-R-LEA

Dani AI

Generated

— keeping both a head and a tail pointer is a perfectly valid design for a singly linked list when you need O(1) appends. That matches ’s point about queues vs stacks: if you always push/pop at one end you may only need a single pointer; if you need fast access to both ends, keep both. ’s idea of back pointers is the doubly-linked option; use that only when you need O(1) removals from the tail or easy backward traversal.

A few practical fixes and invariants that your code needs (these are concrete bugs to avoid): always initialize a new node’s fields before linking it into the list; on an empty-list insert set both head and tail to the new node; use the tail pointer when appending (not the head); check the allocator for failure; and avoid unused parameters — they confuse the API. Pick consistent names: head = first node, tail = last node. If you keep globals, make sure every operation preserves those invariants.

Recommended API patterns:

  • Use two clear operations: insert_head and insert_tail. Each has trivial and well-tested logic.
  • Prefer a small wrapper struct that holds both head and tail rather than loose globals. That makes functions reentrant and easier to test.
  • Alternatively use pointer-to-pointer when you want to update the caller’s head inside a function.

Example of a safe, minimal pattern (wrapper + append):

struct Node { int val; struct Node *next; };
struct List { struct Node *head, *tail; };

/* allocates and initializes a node, returns NULL on failure */
struct Node *make_node(int v) { /* malloc, check, set val and next=NULL */ }

/* append in O(1) */
int append(struct List *L, int v) { struct Node *n = make_node(v); if (!n) return -1;
  if (L->tail) L->tail->next = n, L->tail = n;
  else L->head = L->tail = n;
  return 0;
}

Troubleshooting tips: run with Valgrind to catch leaks and invalid accesses, check every pointer before dereference, and write unit tests for empty, one-element, and many-element cases.

Recommended Answers

All 4 Replies

Member Avatar for 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.

Member Avatar for myk45

Well, i was talking about a singly linked list.

Member Avatar for sree_ec

Well, i was talking about a singly linked list.

could be a good read

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.