Chapter Three Linked List
Chapter Three Linked List
Chapter Three Linked List
07/07/2023 Ataklti N. 1
3.1. Introduction
Data structures can be divided into two types:
Static data structures and dynamic data structures.
Static data structures cannot change their form and its address during
program execution.
Arrays have at least two limitations: their size has to be known and the
data in the array are stored in a continuous block of computer memory.
A linked list is a sequence of data structures and pointer, which are
connected together via links.
07/07/2023 Ataklti N. 2
…Continued
07/07/2023 Ataklti N. 3
Array Vs Linked list
Arrays are suitable for:
– Inserting/deleting an element at the end.
– Randomly accessing any element.
– Searching the list for a particular value.
Linked lists are suitable for:
– Inserting an element.
– Deleting an element.
– Applications where sequential access is required.
07/07/2023 Ataklti N. 4
Types of Linked List
07/07/2023 Ataklti N. 5
3.2. Singly Linked Lists
Linked lists consist of a number of nodes that store data and links to
other nodes.
Because the node contains a link to the next element in the list, nodes
can be located anywhere in memory.
The simplest form of linked list is the singly linked list.
Singly linked list each node contains some data and a single link to its
successor in the list.
A linked list is made up of a chain of nodes.
07/07/2023 Ataklti N. 6
…Continued
Linked lists are the most basic self-referential structures.
Linked lists allow you to have a chain of structs with related data.
Each link is linked with its next link using pointer.
Last link carries a link as null to mark the end of the list.
07/07/2023 Ataklti N. 7
Basic Operations of Linked List
Following are the basic operations supported by a list.
Creating a list Node/new node
Insertion
Display( Reverse)
Deletion
Search
Sorting
07/07/2023 Ataklti N. 8
3.2.1 Creating and Representation
Singly Linked Lists in C++
Now examine how some of the basic linked list operations
can be performed.
07/07/2023 Ataklti N. 9
….Continued
The last node has a link to the special value NULL, which any pointer can
point to, to show that it is the last link in the chain.
There is also another special pointer, can called Start (also called head),
which points to the first link in the chain so that we can keep track of it.
07/07/2023
struct node *start_ptr
Ataklti N.
= NULL; 10
Example
• Example to create Node and Display with their Information's.
07/07/2023 Ataklti N. 11
Insertion a node
07/07/2023 Ataklti N. 12
Insertion At the beginning
Adding a node to the beginning of a linked list is performed in four steps
Create a new Node in memory.
Initialise the info member to a particular Data members
Because the node is being added to the front of the list, the next member
becomes a pointer to the first node of the list, that is, the current value of
start.
The new node now precedes all the nodes in the list, but we need to
update the value of start to reflect this fact.
Therefore, start is made to point to the newly created node
07/07/2023 Ataklti N. 13
Example
Example to create Node , Insert Node at the Beginning and Display
07/07/2023 Ataklti N. 14
Insertion a node to the end
Adding a node to the end of the list consists of five steps
Create a new Node in memory.
Initialise the info member to a particular data members.
Because the node is being added at the end of the list, the next
member is set to null.
The node is included in the list by making the next member of
the last node in the list point to the newly created node
The new node now follows all the nodes in the list, but we
need to update the value of tail to reflect this fact.
Therefore, tail is made to point to the newly created node
07/07/2023 Ataklti N. 15
Example
07/07/2023 Ataklti N. 16
Insert a Node between node
Adding a node to the beginning of a linked list is performed in four
steps
Because the node is being added to between nodes they need two
temporary nodes acting as the previous node and next node by
traversing and counting of the specific position .
The previous node points to the new created node and the new created
node point to the next node
07/07/2023 Ataklti N. 17
Adding Nodes
• When a node is added at the beginning,
– Only one next pointer needs to be modified.
• head is made to point to the new node.
• New node points to the previously first element.
07/07/2023 Ataklti N. 19
Deletion
• Deleting from the top of the list
• Deleting from the end of the list
• Deleting from the middle of the list
07/07/2023 Ataklti N. 20
Delete AT the Head
• The 3 steps used by deleteFromHead to remove the first node of a
list:
• First we remember the location of the first node by making a
temporary variable tmp point to it
• Now we move the head pointer to point to the second node in the
list, which will now be the first node
• Finally, we use the tmp variable to delete the original first node.
07/07/2023 Ataklti N. 21
Delete node from end
• Function deleteFromTail() removes the last element from the list. :
• A temporary variable tmp is set to point to the second-last node in
the list.
• After deletion, this node will become the new tail of the list
• The tail node of the list is deleted
• Because tail is now pointing to a non-existent node, it is set to
point to the new last node, currently pointed to by tmp
• Similarly, the next member of this node is also pointing to nothing.
• Because it is the new last node, its next member is set to null
07/07/2023 Ataklti N. 22
Delete at anywhere(Middle)
• It may be at the beginning, the end or somewhere in the middle of the
list.
• This general case is handled by the function deleteNode(),
• The required node is located in the list, and two pointers are assigned:
• pred is set to point to the predecessor to the node, and tmp is set to
point to the node itself.
• The next member of the node pointed to by pred is made to point to
the successor of the node to be deleted.
• Effectively, we are telling the list to skip out the required
• Finally we use the tmp variable to delete the required node
07/07/2023 Ataklti N. 23
Doubly Linked Lists
• A doubly linked list is one where there are links from each node
in both directions:
07/07/2023 Ataklti N. 24
Continued…
• Each node in the list has two pointers, one to the
next node and one to the previous one - again, the
start and ends of the list are defined by NULL
pointers.
• With the doubly linked list, we can move the
current pointer backwards and forwards at will.
07/07/2023 Ataklti N. 25
Creating Doubly Linked Lists
07/07/2023 Ataklti N. 26
Circular Lists
In some situations, a linked list is needed that forms a ring,
i.e. there are no null pointers to indicate the end of the list,
and each node
Such a structure is called a circular linked list, as a successor
node.
they can be either singly linked or doubly linked
07/07/2023 Ataklti N. 28