Singly Linked List Algorithm Explanation for Mark Allen Weiss Book Implementation

Type declaration for linked list::

Node ::

It represents a structure of node;
It contains element and reference/Pointer to next node.

PtrToNode ::

Pointer to next node.
It is the address of next node.
Also called as reference to the next node.

List L (Header):

It is the Header of the List.
It will not contains element.
L->Next is address of the node which is the first node of list.
If List is empty, L->Next = NULL

Position P:

It is the address of any node which is 1st or 2nd...or last node.
It is mainly used in search operation where we need to get the address of node which matches search key.

ElementType X:

It represents the variable type and value.
The type may be integer, character, float etc,.

List MakeEmpty(List L):

Empty the List.(L is the header of List).

int IsEmpty(List L):

Check whether that the List is Empty or not.(L is the header of List)

int IsLast(Position P, List L):

Check whether that the node available at Position(P) is the last node of the List.

Position Find(ElementType X, List L):

Check whether that the element X available in any node of the List.
If element X available in any node, Function will return the address/reference(Position p) of a particular node.

void Delete (ElementType X, List L):

Delete the node which contains element X.(L is the Header)

Position FindPrevious(ElementType X, List L):

Find the Address of the node which is previous of a node which contains element X.

void Insert(ElementType X, List L, Position P):

Insert the node with element X at position P in List.(L is Header)

void DeleteList(List L):

Delete Entire List. (L is Header)

Position First(List L):

Get the first node of a LIST. (L is Header)

ElementType Retrieve(Position P):

Get the element from the node available at the Position P.

Linked List Representation & Header

Position & Element Type::

IsEmpty::

IsLast::

Find Element::

Find Previous::

Delete Element::

Insert Element::

Common Errors:

1. Memory Access Violation or Segmentation Violation
This message usually means that a pointer variable contains a bogus address.
One common reason is failure to initialize the variable.
For example P is not initialized but We are trying to use P->Next
2. Accessing the pointer which contains NULL value
For Example, If P=NULL. P->Next is not valid.
Whenever you do an indirection, you must make sure that the Pointer is not NULL.
3. When and when not to use malloc to get a new cell.
Declaring the pointer to a structure does not create the structure but only gives enough space to hold the address where some structure may be.
For Example, Position P==> Pointer to Structure only gives enough space to hold the address.
The only way to create a record that is not already declared is to use malloc.
For example, P = malloc (sizeof (struct Node)); will create the space.
If you want to use a pointer variable to run down a list, there is no need to create a new structure. In that case malloc is not required.
For Example, Position P, P->Next is enough for IsEmpty, IsLast functions.
4. When to use free()
When things are no longer needed, you can issue a free command to inform the system that it may reclaim the space.
A consequence of the free(P) command is that the address P is pointing to is unchanged but the data that reside at address are now undefined.
After a deletion in a linked list, it is good idea to free the cell, especially if there are lots of insertions and deletions intermingled and memory might become a problem.
We need to keep a temporary variable set to the cell to be disposed of, because after the pointer moves are finished, you will not have a reference to it.

Reference::

  Data Structure and Algorithm Analysis in C, 2nd Edition, Mark Allen Weiss

Goto Data Structure Concepts

Goto CSR Initiative