Linked List Implementation Options in C

Question

In implementing a single linked list in C, I think there are three ways :

HEADER IS A POINTER ITSELF.IT POINTS TO THE FIRST NODE OF THE LINKED LIST.

1.Declare the header globally and use function void insert(int) to insert.This should work as header is global.

2.Declare header inside main and use function node*insert(node*) to insert.This should work because of the return involved.

3.Declare header inside main and use function void insert(node**) to insert.

Sometimes the second way works even without the return involved. Why?

Which is the better way?

If the functions involved are recursive as in tree which method is appropriate?

I assume that when you wrote "header", what you meant was the head node of the list. The question is quite confusing. — LihO
– LihO, Commented Sep 21, 2013 at 17:04
node* is an implementation detail that should not be part of the interface of the list. — Elazar
– Elazar, Commented Sep 21, 2013 at 17:04
It will work if you don't change the head in the node *insert(node *). — user2778477
– user2778477, Commented Sep 21, 2013 at 17:09
when insert(node*) acts on header which is a pointer itself, then?? will it work without return type? — Rafed Nole
– Rafed Nole, Commented Sep 21, 2013 at 17:11

Joe · Accepted Answer · 2013-09-21 17:04:24Z

2

You should encapsulate your data structure in a single object (the head node or a struct that contains it), and then you can have your functions work on that object. This means that you can have more than one linked list in your program (that won't work with a global head node) and you can also pass it around to different functions that want to use it (there's no point having a data structure without being able to use it).

If you have your single object (head node) stored in your program then the insert and delete functions don't need to return anything, as you already have a pointer to the object that represents the linked list.

answered Sep 21, 2013 at 17:04

Joe

48k37 gold badges166 silver badges261 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rafed Nole Over a year ago

when header is a dummy node it 2nd way should work.When header is a pointer itself then should it work without return type?

Joe Over a year ago

Create two structs, one called node and one called list. The list struct has a node pointer, which can be NULL for an empty list. Even for an empty list, the list node should exist. Now you have no need for dummy nodes.

Elazar · Accepted Answer · 2013-09-21 17:12:50Z

0

If the functions involved are recursive as in tree which method is appropriate?

The functions should not be recursive "as in tree". The depth of a tree is O(logn), which means recursion is reasonable in many situations; The size of a linked list is O(n), which means recursion can easily overflow the stack.

answered Sep 21, 2013 at 17:12

Elazar

22k4 gold badges51 silver badges68 bronze badges

Collectives™ on Stack Overflow

Linked List Implementation Options in C

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related