Linked Lists Vs Arrays

DATA STRUCTURES
AND ALGORITHMS
COURSE CODE: CS-201
INSTRUCTOR: SAHAR ARIF
EMAIL: [email protected]
LINKED LISTS VS ARRAYS
LINKED LISTS
• Linked List is a linear data structure, in which elements are not stored
at a contiguous location, rather they are linked using pointers. Linked
List forms a series of connected nodes, where each node stores the
data and the address of the next node.
• Basic Terminologies of Linked List
• Head: The Head of a linked list is a pointer to the first node or reference of the first node of linked list. This pointer
marks the beginning of the linked list.
• Node: Linked List consists of a series of nodes where each node has two parts: data and next pointer.
• Data: Data is the part of node which stores the information in the linked list.
• Next pointer: Next pointer is the part of the node which points to the next node of the linked list.
• Importance of Linked List
• Here are a few advantages of a linked list that is listed below, it will help you understand why it is necessary to know.
• Dynamic Data structure: The size of memory can be allocated or de-allocated at run time based on the operation
insertion or deletion.
• Ease of Insertion/Deletion: The insertion and deletion of elements are simpler than arrays since no elements need to
be shifted after insertion and deletion, Just the address needed to be updated.
• Efficient Memory Utilization: As we know Linked List is a dynamic data structure the size increases or decreases as per
the requirement so this avoids the wastage of memory.
• Implementation: Various advanced data structures can be implemented using a linked list like a stack, queue, graph,
hash maps, etc.
Example:
In a system, if we maintain a sorted list of IDs in an array id[] = [1000, 1010, 1050, 2000,
2040].
If we want to insert a new ID 1005, then to maintain the sorted order, we have to move all
the elements after 1000 (excluding 1000).
Deletion is also expensive with arrays until unless some special techniques are used. For
example, to delete 1010 in id[],
everything after 1010 has to be moved due to this so much work is being done which affects
the efficiency of the code.
• Types of linked lists:
• There are mainly three types of linked lists:
• Single-linked list
• Double linked list
• Circular linked list
• 1. Single-linked list:
• In a singly linked list, each node contains a reference to the next node
in the sequence. Traversing a singly linked list is done in a forward
direction.
• // Singly linked list node in C++
• class Node {
• public:
•
• // Data field
• int data;
•
• // Pointer to the next node
• Node* next;
• // Constructor to initialize a new node with data

• Node(int new_data) {
• this->data = new_data;
• this->next = nullptr;
• }
• };
• 2. Double-linked list:
• In a doubly linked list, each node contains references to both the next
and previous nodes. This allows for traversal in both forward and
backward directions, but it requires additional memory for the
backward reference.
• // Doubly linked list node in C++
• class Node {
• public:
• // Data field
• int data;
• // Pointer to previous node

• Node* prev;
• // Pointer to the next node

• Node* next;
• // Constructor to initialize a new node with data

• Node(int new_data) {
• this->data = new_data;
• this->next = nullptr;
• this->prev = nullptr;
• }
• };
• 3. Circular linked list:
• In a circular linked list, the last node points back to the head node,
creating a circular structure. It can be either singly or doubly linked.
• Basic Operations in Linked List
• The basic operations in the linked lists are insertion, deletion,
searching, display, and deleting an element at a given key. These
operations are performed on Singly Linked Lists as given below −
• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.
• Operations on Linked Lists
• Insertion: Adding a new node to a linked list involves adjusting the pointers
of the existing nodes to maintain the proper sequence. Insertion can be
performed at the beginning, end, or any position within the list
• Deletion: Removing a node from a linked list requires adjusting the pointers
of the neighboring nodes to bridge the gap left by the deleted node.
Deletion can be performed at the beginning, end, or any position within the
list.
• Searching: Searching for a specific value in a linked list involves traversing
the list from the head node until the value is found or the end of the list is
reached.
• Advantages of Linked List:
• Dynamic nature: Linked lists are used for dynamic memory allocation.
• Memory efficient: Memory consumption of a linked list is efficient as its size can grow or shrink dynamically
according to our requirements, which means effective memory utilization hence, no memory wastage.
• Ease of Insertion and Deletion: Insertion and deletion of nodes are easily implemented in a linked list at any
position.
• Implementation: For the implementation of stacks and queues and for the representation of trees and graphs.
• The linked list can be expanded in constant time.
• Disadvantages of Linked List:
• Memory usage: The use of pointers is more in linked lists hence, complex and requires more memory.
• Accessing a node: Random access is not possible due to dynamic memory allocation.
• Search operation costly: Searching for an element is costly and requires O(n) time complexity.
• Traversing in reverse order: Traversing is more time-consuming and reverse traversing is not possible in singly
linked lists.
• Applications of Linked List:
• Here are some of the applications of a linked list:
• Linear data structures such as stack, queue, and non-linear data
structures such as hash maps, and graphs can be implemented using
linked lists.
• Dynamic memory allocation: We use a linked list of free blocks.
• In web browsers and editors, doubly linked lists can be used to build a
forwards and backward navigation button.
THE END

Linked Lists Vs Arrays

Uploaded by

Copyright:

Available Formats

Linked Lists Vs Arrays

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Linked Lists Vs Arrays

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES

• // Constructor to initialize a new node with data

• // Pointer to previous node

• // Pointer to the next node

• // Constructor to initialize a new node with data

You might also like