Transcript Singly-Linked Lists

Linked Lists
Introduction
• In linked list each item is embedded in a link
• Each item has two parts
– Data
– Pointer to the next item in the list
• Insert, Delete and Edit operations can be
performed
• Each item of the list can only be accessed
through the next pointer, unlike arrays
Graphical Representation
Item 1
Item 2
Item 3
Item 4
Front
Data
Next
Null
Differences between Linked Lists
and Arrays
• The order of linked items maybe different
than the physical storage of the items
• Linked Lists only allow sequential access as
compared to random access in arrays
Types of Linked Lists
Singly-Linked Lists
• Simplest kind of linked lists
• One link per node
• The link points to only the next item in the list
45
21
34
NULL
A singly linked list, contains two values – value of the current node and
a pointer to the next node
Doubly Linked Lists
• Doubly-Linked List or two-way linked list
• Each node has a data value and two links, One
pointing to the next item and second pointing
to the previous item
NULL
12
67
78
NULL
Circularly Linked Lists
• The first and last nodes are linked together
• Circular linked lists can be implemented for
both the singly and doubly linked lists
• Have no start of end
• It is most useful in the cases where you have
one item and want to see all the items
45
21
34
Application of Linked Lists
• Used in implementing other data structures
like, stacks and queues
• In situations where the number of the items
to be added is not known before hand
• A lot of addition and deletion operations are
performed
• Position of the added items is important
Linked Lists vs. Arrays
• Advantages
– Elements can be inserted into linked lists
indefinitely, array will eventually either fill up or
need to be resized, an expensive operation that
may not even be possible if memory is fragmented
– Deletion of items from linked lists does not leave
the list with wasted memory unlike arrays
– Useful in implementing persistent data structure
• A persistent data structure always preserves its
previous version when it is modified
Linked Lists vs. Arrays (contd…)
New Nodes
Old Nodes
NULL
An example of persistent data structure using linked lists
• Disadvantages
– Arrays allow random access Linked lists don’t
– Singly linked lists can only be traversed in one
direction
– Sequential access on arrays is faster than linked
lists due to not using next pointer
Josephus Problem
• A good example to demonstrate the strengths
and weaknesses of linked lists
– The Josephus problem is an election method that works by
having a group of people stand in a circle.
– Starting at a predetermined person, you count around the circle
n times.
– Once you reach nth person, take them out of the circle and have
the members close the circle.
– Then count around the circle the same n times and repeat the
process, until only one person is left.
– That person wins the election.
Josephus Problem (contd…)
• All the people can be seen as a circular linked list
• Deleting any item of the list is only rearranging of
the next pointer, in arrays - an item has to be
deleted and whole list should be resized
• However finding the person will be a difficult task for
linked list as it would a sequential search and needs
to recurse through the list if person is not found.
Whereas is arrays it would be very easy to find nth
item of the array.
Singly Linked List vs. Doubly Linked
Lists
• Doubly linked lists need more space per node
• Doubly linked lists are easy to traverse as it
allows traversal in both directions
• Insert and delet operations on doubly linked
lists are relatively easier, it only requires the
address of the nodes to be operated on
Circular vs. Linear Linked Lists
• Circular linked lists are the most natural
selection for implementing real world circular
objects like people standing in circle
• Circularly linked list allows transversal of the
list starting from any point
• Circularly linked lists allow quick access to first
and last item.
• Main disadvantage of circulary linked lists is its
complex iteration.
Inserting a New Item
Item 1
Item 2
Item 3
Item 4
Front
Data
Next
New Item
Null
Graphical Depiction
Item 1
Item 2
Item 3
Item 4
Front
Data
Next
Null
Deleting an Item
Item 1
Item 2
Item 3
Item 4
Front
Data
Next
Null
Typical Implementation
• struct node {
double data;
node* next;
};
• As this data structure points to its own type structure therefore its
called “self referential”
class node {
private:
double data;
node* next;
public:
getnext();
addnode(node *n);
deletenode(node *n);
};