How would we find an element in a linked list?

A linked list is an algorithm for storing a list of items.

A very good way to think about a linked list is to picture a train, the first node will be the motor of the train and the pointer which is the connector between elements in the linked list, will be in this case the connector between the cars in the train. When we get to the last car of the train (node) we will still have the option to add another car if we decide to do so by setting a pointer to that next car.

An element in a linked list is found by doing a sequential search, we will start by the first node or the motor of the train and from there we will go through every single node in the list until we find what we are looking for.

A couple of examples of how a linked list will look like are:

The next piece of code is an example of how to create a linked list and how we will be going through it.


	/* Program to illustrate traversing a list */
	#include <stdio.h>
	struct list {
		int         value;
		struct list *next;
	};

	main()
	{
		struct list n1, n2, n3, n4;
		struct list *list_pointer = &n1;

		n1.value = 100;
		n1.next = &n2;
		n2.value = 200;
		n2.next = &n3;
		n3.value = 300;
		n3.next = &n4;
		n4.value = 400;
		n4.next = 0;


		while( list_pointer != 0 )  {
			printf("%d\n", list_pointer->value);
			list_pointer = list_pointer->next;
		}
	}
The process of finding anode in linked list can be explained in four easy steps.

Set a pointer to point to the same thing as the start pointer.
If the pointer points to NULL, display the message "End of list" and stop.
Otherwise compare info you are looking for with info from the node pointed to by the start pointer.
if this is not the node you are looking for go the next until you find the node you are looking for.

Some good references are:

linked list

http://www.cprogramming.com/tutorial/lesson15.html

Ask the C++

http://gethelp.devx.com/techtips/cpp_pro/10min/10min0599.asp

C Programming

http://goforit.unk.edu/cprogram/c_087.htm

Some review questions:

1. How do you end a linked list?

a) with a null value

b) with the last node

c) doesn't need to be end.

(ans. a)

2. How do you start a linked list?

a) head node

b) linked list don't have a starting node

c) with a null value

(ans. a)

3. How do we find an element in a linked list?

We go through every single element until we find what we are looking for

4. What is the main advantage of a linked list over an array?

A linked list allows you to easily insert or delete a node to the list, when this is lot harder to do in an array.