[go: up one dir, main page]
Scribd
Upload
9 views6 pages

Linked_List_Tutorial

A linked list is a dynamic data structure consisting of nodes connected by pointers, allowing for flexible size and efficient insertions and deletions. There are three main types of linked lists: singly, doubly, and circular, each with distinct characteristics. While linked lists offer advantages like dynamic memory allocation and ease of implementing other data structures, they also have drawbacks such as increased memory usage and slower access times.

Uploaded by

Taosiful Akash
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views6 pages

Linked_List_Tutorial

A linked list is a dynamic data structure consisting of nodes connected by pointers, allowing for flexible size and efficient insertions and deletions. There are three main types of linked lists: singly, doubly, and circular, each with distinct characteristics. While linked lists offer advantages like dynamic memory allocation and ease of implementing other data structures, they also have drawbacks such as increased memory usage and slower access times.

Uploaded by

Taosiful Akash
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Linked List Tutorial

What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are connected using pointers.

Unlike arrays, linked lists do not have a fixed size, which means they can dynamically grow or shrink

as elements are added or removed. Each node in a linked list contains two parts:

1. Data: The actual data or value of the node.

2. Next: A reference or pointer to the next node in the list.

Types of Linked Lists:

1. Singly Linked List: Each node contains data and a reference to the next node in the sequence.

2. Doubly Linked List: Each node contains data, a reference to the next node, and a reference to the

previous node.

3. Circular Linked List: The last node points back to the first node, creating a loop.

Basic Operations on Linked Lists:

1. Insertion: Adding a new node to the list.

- At the beginning (head insertion)

- At the end (tail insertion)

- After a given node

2. Deletion: Removing a node from the list.

- From the beginning (head deletion)

- From the end (tail deletion)

- From a specific position


3. Traversal: Visiting each node in the list to access the data.

4. Searching: Finding a node with a particular value.

Implementation of a Singly Linked List in C#:

using System;

public class Node

public int Data;

public Node Next;

public Node(int data)

Data = data;

Next = null;

public class LinkedList

private Node head;

// Add node at the end

public void Add(int data)

{
Node newNode = new Node(data);

if (head == null)

head = newNode;

else

Node temp = head;

while (temp.Next != null)

temp = temp.Next;

temp.Next = newNode;

// Display all nodes

public void Display()

Node temp = head;

while (temp != null)

Console.Write(temp.Data + " ");

temp = temp.Next;

Console.WriteLine();
}

// Search for a node

public bool Search(int value)

Node temp = head;

while (temp != null)

if (temp.Data == value)

return true;

temp = temp.Next;

return false;

// Delete node from the beginning

public void Delete()

if (head != null)

head = head.Next;

}
class Program

static void Main()

LinkedList list = new LinkedList();

list.Add(10);

list.Add(20);

list.Add(30);

Console.WriteLine("Linked List: ");

list.Display();

Console.WriteLine("Search for 20: " + list.Search(20));

Console.WriteLine("Search for 40: " + list.Search(40));

list.Delete();

Console.WriteLine("Linked List after deletion: ");

list.Display();

Advantages of Linked Lists:

1. Dynamic Size: Unlike arrays, the size of the linked list can grow or shrink dynamically.

2. Efficient Insertions and Deletions: Inserting or deleting nodes, especially at the beginning, is

faster than with arrays.


Disadvantages of Linked Lists:

1. Memory Usage: Each node requires extra memory to store the reference to the next (or previous)

node.

2. No Random Access: To access a node, you must traverse the list from the head, making random

access slower (O(n) time complexity).

Applications of Linked Lists:

- Dynamic Memory Allocation: Linked lists are often used in dynamic memory allocation systems

where memory needs to be allocated and deallocated dynamically.

- Implementing Stacks and Queues: Linked lists can be used to implement other data structures like

stacks and queues.

- Graph Representation: In graph algorithms, linked lists are used to represent adjacency lists.

Conclusion:

Linked lists are a fundamental data structure that provide flexibility with dynamic size and efficient

insertions/deletions. They are especially useful when memory allocation needs to be flexible and

when frequent changes are made to the data. However, they come with trade-offs such as

increased memory usage and slower access times.

You might also like