** Linked List in C Language Tutorial Notes Study Material with Examples**

**Linked List**

It is a special data structure in which data elements are linked to one another. *Here, each element is called a node which has two parts*

- Info part which stores the information.
- Address or pointer part which holds the address of next element of same

type.

Linked list is also known as **self referential structure.**

**Struct linked_list_node**

**{**

**int info;**

**struct linked_list_node *next ;**

**};**

Syntax of declaring a node which contains two fields in it one is for storing information and another is for storing address of other node, so that one can traverse the list.

**Note: **Last node of a linked list contains NULL value in its address field.

** ****Advantages of Linked List**

- Linked lists are dynamic data structure as they can grow and shrink during the execution time.

- Efficient memory utilization because here memory is not pre-allocated.
- Insertions and deletions can be done very easily at the desired

**Disadvantages of Linked List**

- More memory is required, if the number of fields are more.
- Access to an arbitrary data item is time consuming

## **Type****s ***of ***Linked List**

*of*

These are different types of linked list as given below

**Singly Linked List**

In this type of linked list, each node has only one address field which points to the next node. So, the main disadvantage of this type of list is that we can’t access the predecessor of node from the the current node.

**Doubly Linked List**

Each node of linked list is having two address fields (or links) which help in accessing both the successor node (next node) and predecessor node (previous node).

**Circular Linked List**

It has address of first node in the link (or address) field of last node.

**Key Points**

**Null Pointer**Address field of the last node contains NULL value to indicate the end of list.**External Pointer**(Start Node) Pointer to the very first node of a linked list, it enables us to access the entire linked list.**Empty List**If the nodes are not present in the list, it is empty list or NULL list. The value of the external pointer/start pointer will be NULL for an empty list.

Start =NULL;

**Circular Doubly Linked List**

It has both the previous and next pointer in circular manner.

**Operations on Linked Lists**

The following operations involve in linked list are as given below

**Creation**

Used to create a linked list.

**Insertion**

Used to insert a new node in linked list at the specified position. *A *new

*node may be inserted*

**At the beginning of a linked list****At the end of a linked list****At the specified position in a linked list****if ease of empty list, a new node is inserted as a first node.**

**Deletion**

This operation is basically used to delete as item (a node). A node may be deleted from the

**Beginning of a linked list.****End of a linked list.****Specified position in the list.**

**Traversing**

It is a process of going through (accessing) all the nodes of a linked list from one end to the other end.

**Memory Allocation: Garbage Collection ****in Linked List**

There should be some mechanisms

- Which provides unused memory space for new nodes.
*Which*makes available the memory space of deleted nodes for future

use.

**Situation of Overflow and Underflow**

Suppose, someone wants to insert new data into a data structure but there is no available space *i.e., *the free storage list is empty. This situation is usually called

**OVERFLOW. **The situation, where one wants to delete data from a data structure that is empty is referred as UNDERFLOW.

If START = NULL and someone still wants to delete data, then UNDERFLOW situation occurs.

**Key Points**

- Together with the linked lists in memory, a special list is maintained which consists of unused memory cells.
- The special list list has it’s own pointer and is called the “List of Available Space ” or the “Free Storage List ” or the “Free Pool”.

**Insertion of a Node at Specific Position in a Linked List**

The next pointer field of Node *A *now points to the new Node *N, *to which

AVAIL previously pointed. AVAIL now points to the second node in the free pool, to which Node *N *previously pointed.

The next pointer field of Node *N *now points to Node *B *to which Node *A*

previously pointed. Suppose, we are given the value of LOC, where either LOC is the location of a Node *A *in a linked list or LOC = NULL.

*N = *New node whose location is NEW

We need to insert ITEM into list, so that ITEM follows Node *A *or *when *LOC = NULL, so that ITEM is first node. If LOC is not NULL, then *we let *Node *N *point to Node *B *(which originally followed Node *A) *b_{y}* the *assignment.

**LINK [NEW] = LINK [LOC]**

and we let Node A point to the new Node *N *by the *assignment. *

**LINK [LOC] = NEW**

**Deletion from a Linked List**

In the above diagram, the three pointer fields are changed as follows

- The next pointer field of Node
*A*now points to Node*B,*where Node*ti*

previously pointed.

- The next pointer field of
*N*now points to the original first node in free pool, where AVAIL previously pointed. - AVAIL new points to the deleted Node
**Polynomials**(An Application of Linked Lists)

**A polynomial p(x) = 2x ^{5} — 3x^{4} — 9x^{2} + 4, may be represented by list,** where

each node corresponds to a non-zero term of *p(x).*

The information part of the node is divided into two fields representing, the coefficient and the exponent of the corresponding term, respectively. All nodes are linked according to decreasing degree.

# Importance of Turing Machine Tutorial Notes Study Material with Examples

Follow Us on Social Platforms to get Updated : **twiter, ****facebook, Google Plus**

Learn Turing Machine in Handbook Series: **Click here **