DS – Single Linked List

Linked List:

• Linked List stores information in the form of nodes.
• Nodes get memory in random locations and connected using links(pointers)
• Insertions and Deletions are faster compared to Array (Array List)
• Inserting and deleting nodes depends on connections.

Singly Linked List:

• Every Node has 2 Fields
  • Data field
  • Link field
• Link Filed is pointer type
• Data means int, float, structure…….
• Last node link is NULL – No other record to connect.

Node creation using structure:

	struct Node{
		int data;
		struct Node* link;
	};
	struct Node *root = NULL;

Root variable:

• “root” is a variable need to create globally to structure.
  • struct Node* root = NULL
• This ‘root’ variable can be accessed though out the program from all functions, hence it is GLOBAL VARIABLE.
• “root” is always pointing to First Node in the List.

Allocate memory to Node dynamically:

• Node is structure type.
• We use malloc() function to allocate memory to structures.
• Once memory allocated, malloc function returns base address of memory blck as void*.
• We need to convert the void* type into struct Node* type.

Append():

• Adding a node at the end of existing list is called “Append”.
• If no nodes in the list, newly created node become first node or root node.
• If list is not empty, we need to add the node at the end.

Creation of List:

• In this mode case, we create elements continuously until user want to stop.
• We use while loop for this creation.
• We always maintain the last node address to add the new address to List.

Finding the length of List:

• Define a variable inside the length function with value 0
• Repeat the loop until it reaches null and increase count value by one every time.
• Return the count from the length() function.

Display node values:

• Check the list is empty or not.
• If the list is not empty, display all node values until it reaches NULL value.

Adding node at front:

Search for element in List: we use linear search algorithm for searching specified element

Inserting element after specified element in the List:

Removing the node from the List: calling the free() function always disconnect the pointer to location, hence the memory allocates to other node.

Note: Make sure that the node not connected to any other node before invoke free() function

Removing first node in the list:

removeAfter():

• Read node location.
• If loc greater then length, return with error message
• If loc is present, make the pointer pointing to that location.
• Maintain the pointer to previous node of specified location to connect with next node of location node.