Dynamic Implementation

Linked list is a data structure used for storing collections of data. Linked list has the following properties:

• Successive elements are connected by pointers
• Last element points to NULL
• Can grow or shrink in size during execution of a process
• Can be made just as long as required
• It does not waste memory space

Each element (we will call it a node) of a linked listcomprisesof two items - the data and a reference to the next node.The entry point into the linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

A linked list is a dynamic data structure i.e. the number of nodes in a list is not fixed and can grow and shrink on demand. Any application dealing with an unknown number of objects will need to use a linked list.

One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If wewant to access a particular item then wehave to start at the head and follow the references until weget to that item.

Another disadvantage is that a linked list uses more memory compare with an array - where extra 4 bytes (on 32-bit CPU) is required to store a reference to the next node.

Dynamic Implementation in C

//linked list representation

struct Node{

int value;

struct Node* next;

};

The above code snippet shows the representation of a linked list in C programming language. It is implemented as a structure. Here, the Node has two fields, the value (the data that it holds) and the Node* next which is the pointer reference to another node.

Node creation:

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node);

From the above code, the pointer newNode contains the address of a newly created node. If the linked list is empty and first node is created then it is also known as head node.

Once created, it can be assigned the value and its next pointer is assigned to the address of the next node. If no next node exists, it is assigned to NULL.

. . .

. . .

newNode ->value = value;

newNode -> next = Null;

. . .

. . .

The deletion works by removing the reference to the next node. To add a new node in between the list, it has to be referenced by the next pointer of a node in the list.In this way, the linked list can grow or shrink in size dynamically.

References:

1.http://www.thegeekstuff.com/2012/08/c-linked-list-example/

2.https://en.wikipedia.org/wiki/Linked_list

3. Karumanchi, N. "Data Structures and Algorithms Made Easy"

4. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

.