List 

A list can be defined as a finite collection of data elements. The elements that constitute the list are known as list items. In general, a list can be defined as 

L={a1,a2,a3,....,an }

Where a1,a2,a3,....,an = ai  are list items

A list is a very common data structure that has a wide variety of applications.

For implementation, we can assume that the list items belong to the same type of items (homogeneous nature) or of the same data types.

A list can be treated as a finite collection of homogeneous data items. Such a list can be implemented using arrays.

Operations:

The common operation which can be characterised for list data items are as follows:

1. Checking for an empty list

2. Checking for a full list

3. Inserting a new element

4. Deleting an element

5. Searching for a particular element

6. Finding the length of a list

7. Merging list

8. Concatenation of a list

9. List traversal

10. Displaying a list

Need for Dynamic Implementation of List

When a List is implemented using an Array, the problem of overflow is always associated with it. This is because an array is a finite structure. Its size must be declared in advance.

For example, if an array is declared with size 10, it can store only 10 elements. When all the 10 slots are occupied and we try to insert a new element, an overflow condition occurs. This can happen even when free memory is available in the computer system.

One solution is to declare an array with a large size. This can postpone the overflow problem. However, it may result in memory wastage because the memory allocated to the array remains reserved for that array and cannot be easily used for another purpose.

Therefore, we need an implementation in which:

1. The maximum size of the List is not fixed in advance.

2. A new element can be inserted whenever free memory is available.

3. When an element is deleted, the memory occupied by it should be released.

4. The released memory should be returned to the computer system so that it can be used for other purposes.

This is possible through dynamic memory allocation.

In the C language, dynamic memory allocation is performed using pointers and functions such as:

• malloc() — allocates memory dynamically.

• free() — releases dynamically allocated memory.

Thus, a linked list is commonly used to implement a List dynamically because it can grow and shrink according to the available memory.

Linked List

A linked list can be defined as a collection of nodes where each node consists of two parts:

1. Info Part or Data Part

2. Next Part or Pointer Part or Next Address Part

In a linked list, the physical and logical ordering of nodes need not be the same.

For example, nodes may be stored at different memory locations, but the Next pointer connects them in the required logical sequence.

Operations on a Linked List

1. Declaration of a linked-list node.

2. Initialization of the linked list.

3. Checking whether the list is empty.

4. Insertion of a node into the linked list.

5. Deletion of a node from the linked list.

6. Searching for an item in the linked list.

7. Traversing the linked list.

8. Concatenation of two linked lists.

9. Merging two linked lists.

10. Counting the number of nodes in the linked list.

11. Insertion at different positions:

    1. At the beginning

    2. At the end

    3. Before a selected node

    4. After a selected node

    5. At a specified position

12. Deletion from different positions:

    1. From the beginning

    2. From the end

    3. From anywhere in the list

13. Updating the information stored in a node.

Advantages of a Linked List over an Array-Based List

1. No Fixed Size

A linked list does not require a fixed size to be declared in advance.

Memory is allocated dynamically as new nodes are required.

2. Easy Insertion

A new node can be inserted by changing the required links.

Existing nodes do not need to be shifted, as they are in an array.

3. Easy Deletion

A node can be deleted by changing the links between the surrounding nodes.

Other nodes do not need to be shifted.

4. Better Memory Utilisation

Memory is allocated when a node is required.

Therefore, unused pre-allocated array space can be avoided.

However, each node requires additional memory for storing the pointer.

5. Dynamic Structure

The size of a linked list can grow or shrink during program execution, subject to the availability of memory.

6. Useful for Implementing Other Data Structures

Linked lists can be used to implement several other data structures, such as:

1. Linked Stack

2. Linked Queue

3. Sparse Matrix

4. Polynomial Representation

Important Note about Overflow

It is not technically correct to say: "A linked list has no overflow problem."

A linked list can also become full when the system is unable to allocate additional memory. A more accurate statement is:

"A linked list does not have the fixed-size overflow problem associated with a statically allocated array."

Thus, an array may report overflow when its allocated capacity is exhausted, even if additional memory is available elsewhere in the system. A linked list can dynamically request memory for new nodes, provided sufficient memory is available.

Algorithm: Insertion in Between a Linked List

Purpose: Insert a new node after the node containing the value val.

Algorithm:

1. ptr = list

2. While (ptr != NULL), repeat Steps 3 to 5.

3. If (Info(ptr) == val), then:

   1. x = new node

   2. Read(Info(x))

   3. Next(x) = Next(ptr)

   4. Next(ptr) = x

   5. Exit (if only one insertion is required)

4. ptr = Next(ptr)

5. End While

6. End of Algorithm

The two important statements are:

Next(x)   = Next(ptr)

Next(ptr) = x

This first connects the new node X to the next node, and then connects ptr to X.

Important: If the algorithm is intended to insert only one node, use Exit after insertion. Otherwise, the traversal may continue and potentially perform additional insertions.

Algorithm: Insertion of a Data Item Before a Selected Node

Purpose: Insert a new node before the node containing the selected value val in a singly linked list.

Algorithm:

1. ptr = list

2. prev = NULL

3. While (ptr != NULL), repeat Steps 4 to 7.

4. If (Info(ptr) == val), then:

   1. x = new node

   2. Read(Info(x))

   3. Next(x) = ptr

   4. If (prev == NULL), then:

list = x

Otherwise:

Next(prev) = x

5. Exit

5. prev = ptr

6. ptr = Next(ptr)

7. End While

8. End of Algorithm

Algorithm: Deletion of a Node from a Linked List

Purpose: Delete the node containing a selected value val from a singly linked list.

Algorithm:

1. ptr = list

2. prev = NULL

3. If (list == NULL), then

   • Print "Underflow / List is Empty"

   • Go to Step 9

4. While (ptr != NULL), repeat Steps 5 to 7.

5. If (Info(ptr) == val), then:

   • If (prev == NULL), then
     list = Next(ptr)

   • Otherwise,
     Next(prev) = Next(ptr)

   • Free(ptr)

   • Exit

6. prev = ptr

7. ptr = Next(ptr)

8. End While

9. Print "Node not found"

10. End of Algorithm

Linked List and block chain

A blockchain can be conceptually understood as a chain of data blocks, similar to how a linked list is a chain of nodes. However, blockchain extends this basic chaining idea with cryptographic hashing, authentication, distributed storage, and consensus mechanisms. 

A Linked List can be used to introduce the basic structural concept of a Blockchain, but it should not be called a blockchain itself.

The easiest way to explain the relationship is shown in following table:

Linked List Concept

Blockchain Concept

Node

Block

Data in node

Data/transactions in block

Next pointer

Reference to previous block

Node address/reference

Cryptographic hash

Head node

Genesis block

Last node

Latest block

Sequence of nodes

Chain of blocks

Link between nodes

Cryptographic link between blocks

Insertion of node

Addition of a new block

Traversal of nodes

Verification/tracing of blocks

Concept

Linked List

Blockchain

Conceptual Similarity

Basic Structure

Collection of connected nodes

Collection of connected blocks

Both form a chain of connected elements

Element

Node

Block

Both contain a unit of data

Data Storage

Data stored inside each node

Transactions/data stored inside each block

Both store data in individual units

Link

Next pointer/reference

Previous block hash

Both maintain a link to another element

Sequential Order

Nodes have a logical sequence

Blocks have a chronological sequence

Both maintain an ordered sequence

First Element

Head node

Genesis block

Both have a starting element

Last Element

Last node generally points to NULL

Latest block points logically to its predecessor through hash

Both have a current/end element

Traversal

Start from head and follow links

Start from a block and follow hash references

Both can be traversed through links

Insertion

New node can be added

New block can be added to the chain

Both support addition of new elements

Relationship

Node A → Node B

Block A → Block B

Each element is related to another element

Chain Dependency

Changing links can affect list structure

Changing block data changes its hash and affects the chain

Both have dependency between connected elements

Dynamic Growth

List can grow by adding nodes

Blockchain grows by adding blocks

Both can grow dynamically

Representation

Data + Pointer

Data + Hash/Metadata

Both combine content with linking information

Linked List vs. Blockchain 

Basis

Linked List

Blockchain

Basic concept

A linear data structure made of nodes

A distributed digital ledger made of blocks

Main unit

Node

Block

Structure

Data + Next Pointer

Transactions + Timestamp + Previous Hash + Current Hash

Connection

Nodes are connected using pointers/addresses

Blocks are connected using cryptographic hashes

Example

Node1 → Node2 → Node3 → NULL

Block1 → Block2 → Block3 → Block4

Direction

Usually one-way or two-way

Generally follows a chronological chain

Data modification

Data can normally be modified by a program

Changing confirmed data changes the block hash and affects subsequent blocks

Security

No inherent cryptographic security

Uses cryptographic hashing and digital signatures

Centralization

Usually controlled by one program/system

Often decentralized across multiple participating computers

Copy of data

Normally one data structure in memory/storage

Multiple participants may maintain copies of the ledger

Validation

Program controls insertion/deletion

Network consensus mechanisms validate transactions/blocks

Insertion

Can insert a node at different positions

New blocks are normally added to the end of the chain

Deletion

Nodes can be deleted

Historical blocks are generally not simply deleted

Purpose

Efficient organization and manipulation of data

Secure, shared, and tamper-evident record keeping

Typical applications

Stacks, queues, playlists, memory management

Cryptocurrency,

Supply-chain records, 

Digital assets

Key technology

Pointers/references

Cryptographic hashing

 +

 distributed ledger

 +

 consensus

Finding a Cycle in a Linked List

A cycle exists in a linked list when a node's next pointer points back to an earlier node instead of eventually pointing to NULL.

1. Example

Normal Linked List

10 → 20 → 30 → 40 → NULL

Linked List with Cycle

10 → 20 → 30 → 40

                  ↑            |

                   |______|

Here, 40 points back to 30. Therefore, a cycle exists.

2. Process: Floyd's Cycle Detection Algorithm

The most common method is the Slow and Fast Pointer technique, also called Floyd's Cycle Detection Algorithm.

Use two pointers:

1. slow moves one node at a time

2. fast moves two nodes at a time

Algorithm

1. Set slow = head.

2. Set fast = head.

3. Repeat while fast != NULL and fast->next != NULL:

4. Move slow one step.

5. Move fast two steps.

6. If slow == fast, a cycle exists.

7. If fast == NULL or fast->next == NULL, no cycle exists.

Dry Run

10 → 20 → 30 → 40 → 50

                 ↑              |

                 └──── ─  ──┘

Step

Slow

Fast

Start

10

10

1

20

30

2

30

50

3

40

40

4

50

30

5

30

50

...

...

...

Eventually:

slow == fast

Therefore, cycle exists.

C Structure

struct node

{

    int info;

    struct node *next;

};

C Function to Detect Cycle

int hasCycle(struct node *head)

{

    struct node *slow;

    struct node *fast;

    slow = head;

    fast = head;

    while (fast != NULL && fast->next != NULL)

    {

        slow = slow->next;

        fast = fast->next->next;

        if (slow == fast)

        {

            return 1;

        }

    }

    return 0;

}

Function Header :  int hasCycle(struct node *head) 

Components Of Function Header 

Part

Meaning

int

Function returns 1 or 0

hasCycle

Function name

struct node *head

Pointer to first node

1

Cycle found

0

No cycle

Calling the Function

if (hasCycle(head))

    printf("Cycle exists");

else

    printf("No cycle");

Logic in One Line

slow → 1 step

fast → 2 steps

If slow == fast

      ↓

Cycle exists

If there is no cycle, fast eventually reaches NULL.

If there is a cycle, both pointers enter the cycle. Since fast moves faster than slow, it eventually catches up with slow, making:

slow == fast

Time Complexity: O(n)

Space Complexity: O(1)

This is particularly useful for teaching because it demonstrates pointer manipulation, traversal, conditions, and algorithm analysis together.