UNIT-3
LINKED LISTS
Linked lists and arrays are similar since they both store collections of data. Array is the most common
data structure used to store collections of elements. Arrays are convenient to declare and provide the easy
syntax to access any element by its index number. Once the array is set up, access to any element is
convenient and fast.
The disadvantages of arrays are:
• The size of the array is fixed. Most often this size is specified at compile time. This makes the
programmers to allocate arrays, which seems "large enough" than required.
• Inserting new elements at the front is potentially expensive because existing elements need to be
shifted over to make room.
• Deleting an element from an array is not possible. Linked lists have their own strengths and
weaknesses, but they happen to be strong where arrays are weak.
Generally array's allocates the memory for all its elements in one block whereas linked lists use
an entirely different strategy. Linked lists allocate memory for each element separately and only
when necessary.
Linked List Concepts:
A linked list is a non-sequential collection of data items. It is a dynamic data structure. For every data
item in a linked list, there is an associated pointer that would give the memory location of the next data
item in the linked list. The data items in the linked list are not in consecutive memory locations. They
may be anywhere, but the accessing of these data items is easier as each data item contains the address of
the next data item.
Advantages of linked lists:
Linked lists have many advantages. Some of the very important advantages are:
1. Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a
program.
2. Linked lists have efficient memory utilization. Here, memory is not preallocated. Memory is
allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.
3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data
item at a specified position and deletion of the data item from the given position.
4. Many complex applications can be easily carried out with linked lists.
Disadvantages of linked lists:
1. It consumes more space because every node requires a additional pointer to store address of the
next node.
2. Searching a particular element in list is difficult and also time consuming.
Types of Linked Lists:
Basically we can put linked lists into the following four items:
1. Single Linked List.
2. Double Linked List.
3. Circular Linked List.
55
4. Circular Double Linked List.
A single linked list is one in which all nodes are linked together in some sequential manner. Hence, it is
also called as linear linked list.
A double linked list is one in which all nodes are linked together by multiple links which helps in
accessing both the successor node (next node) and predecessor node (previous node) from any arbitrary
node within the list. Therefore each node in a double linked list has two link fields (pointers) to point to
the left node (previous) and the right node (next). This helps to traverse in forward direction and
backward direction.
A circular linked list is one, which has no beginning and no end. A single linked list can be made a
circular linked list by simply storing address of the very first node in the link field of the last node.
A circular double linked list is one, which has both the successor pointer and predecessor pointer in the
circular manner.
56
Applications of linked list:
1. Linked lists are used to represent and manipulate polynomial. Polynomials are expression containing
terms with non zero coefficient and exponents. For example: P(x) = a0 Xn + a1 Xn-1 + …… + an-1
X + an
2. Represent very large numbers and operations of the large number such as addition, multiplication and
division.
3. Linked lists are to implement stack, queue, trees and graphs. 4. Implement the symbol table in
compiler construction.
Single Linked List:
A linked list allocates space for each element separately in its own block of memory called a "node". The
list gets an overall structure by using pointers to connect all its nodes together like the links in a chain.
Each node contains two fields; a "data" field to store whatever element, and a "next" field which is a
pointer used to link to the next node. Each node is allocated in the heap using malloc(), so the node
memory continues to exist until it is explicitly de-allocated using free(). The front of the list is a pointer to
the “start” node.
A single linked list
The beginning of the linked list is stored in a "start" pointer which points to the first node. The first node
contains a pointer to the second node. The second node contains a pointer to the third node, ... and so on.
The last node in the list has its next field set to NULL to mark the end of the list. Code can access any
node in the list by starting at the start and following the next pointers.
The start pointer is an ordinary local pointer variable, so it is drawn separately on the left top to show that
it is in the stack. The list nodes are drawn on the right to show that they are allocated in the heap.
The basic operations in a single linked list are:
• Creation.
• Insertion.
• Deletion.
• Traversing.
Creating a node for Single Linked List:
Creating a singly linked list starts with creating a node. Sufficient memory has to be allocated for creating
a node. The information is stored in the memory.
57
Insertion of a Node:
One of the most primitive operations that can be done in a singly linked list is the insertion of a node.
Memory is to be allocated for the new node (in a similar way that is done while creating a list) before
reading the data. The new node will contain empty data field and empty next field. The data field of the
new node is then stored with the information read from the user. The next field of the new node is
assigned to NULL. The new node can then be inserted at three different places namely:
• Inserting a node at the beginning.
• Inserting a node at the end.
• Inserting a node at intermediate position.
Inserting a node at the beginning.
Inserting a node at the end:
58
Inserting a node into the single linked list at a specified intermediate position other than
beginning and end.
Deletion of a node:
Another primitive operation that can be done in a singly linked list is the deletion of a node. Memory is
to be released for the node to be deleted. A node can be deleted from the list from three different places
namely.
• Deleting a node at the beginning.
• Deleting a node at the end.
• Deleting a node at intermediate position.
Deleting a node at the beginning:
59
Deleting a node at the end:
Deleting a node at Intermediate position:
The following steps are followed, to delete a node from an intermediate position in the list (List must
contain more than two node).
Traversal and displaying a list (Left to Right):
To display the information, you have to traverse (move) a linked list, node by node from the first node,
until the end of the list is reached.
Traversing a list involves the following steps:
• Assign the address of start pointer to a temp pointer.
• Display the information from the data field of each node. The function traverse () is used for traversing
and displaying the information stored in the list from left to right.
Source Code for creating and inserting the Implementation of Single Linked List:
class Item:
'''An Item that stores the data of a Linked List'''
def __init__(self, data):
'''Initializes the data of the Item'''
self._content = data # non-public data
self.next = None
class SingleLikedList:
'''Single Linked List Implementation'''
def __init__(self):
self._start = None
60
self._count = 0
def getItemAtIndex(self, pos):
if self._start == None:
return None
i=0
cursor = self._start
while cursor != None:
if i == pos:
return cursor
i += 1
cursor = cursor.next
return None
def insert(self, data, pos = 0):
item = Item(data)
if self._start == None:
self._start = item
else:
cursor = self.getItemAtIndex(pos)
item.next = cursor.next
item.next = cursor.next
cursor.next = item
self._count += 1
def display(self):
cursor = self._start
while cursor != None:
print(cursor._content, end=' ')
cursor = cursor.next
l = SingleLikedList()
l.insert(10)
l.insert(20)
61
l.insert(30)
l.insert(40)
l.insert(50, 3)
l.display()
Source Code for creating , inserting ,deleting the Implementation of Single Linked List:
class Node(object):
def __init__(self, data=None, next_node=None):
self.data = data
self.next_node = next_node
def get_data(self):
return self.data
def get_next(self):
return self.next_node
def set_next(self, new_next):
self.next_node = new_next
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def insert(self, data):
new_node = Node(data)
new_node.set_next(self.head)
self.head = new_node
def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.get_next()
return count
def search(self, data):
current = self.head
found = False
62
while current and found is False:
if current.get_data() == data:
found = True
else:
current = current.get_next()
if current is None:
raise ValueError("Data not in list")
return current
def delete(self, data):
current = self.head
previous = None
found = False
while current and found is False:
if current.get_data() == data:
found = True
else:
previous = current
current = current.get_next()
if current is None:
raise ValueError("Data not in list")
if previous is None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())
Source Code for creating , inserting ,deleting the Implementation of Single Linked List:
import sys
import os.path
sys.path.append(os.path.join(os.path.abspath(os.pardir), "/home/satya/PycharmProjects/DataStractures"))
from LinkedList2 import LinkedList
import unittest
class TestLinkedList(unittest.TestCase):
def setUp(self):
self.list = LinkedList()
def tearDown(self):
63
self.list = None
def test_insert(self):
self.list.insert("David")
self.assertTrue(self.list.head.get_data() == "David")
self.assertTrue(self.list.head.get_next() is None)
def test_insert_two(self):
self.list.insert("David")
self.list.insert("Thomas")
self.assertTrue(self.list.head.get_data() == "Thomas")
head_next = self.list.head.get_next()
self.assertTrue(head_next.get_data() == "David")
def test_nextNode(self):
self.list.insert("Jacob")
self.list.insert("Pallymay")
self.list.insert("Rasmus")
self.assertTrue(self.list.head.get_data() == "Rasmus")
head_next = self.list.head.get_next()
self.assertTrue(head_next.get_data() == "Pallymay")
last = head_next.get_next()
self.assertTrue(last.get_data() == "Jacob")
def test_positive_search(self):
self.list.insert("Jacob")
self.list.insert("Pallymay")
self.list.insert("Rasmus")
found = self.list.search("Jacob")
self.assertTrue(found.get_data() == "Jacob")
found = self.list.search("Pallymay")
self.assertTrue(found.get_data() == "Pallymay")
found = self.list.search("Jacob")
self.assertTrue(found.get_data() == "Jacob")
def test_searchNone(self):
self.list.insert("Jacob")
self.list.insert("Pallymay")
# make sure reg search works
found = self.list.search("Jacob")
64
self.assertTrue(found.get_data() == "Jacob")
with self.assertRaises(ValueError):
self.list.search("Vincent")
def test_delete(self):
self.list.insert("Jacob")
self.list.insert("Pallymay")
self.list.insert("Rasmus")
# Delete the list head
self.list.delete("Rasmus")
self.assertTrue(self.list.head.get_data() == "Pallymay")
# Delete the list tail
self.list.delete("Jacob")
self.assertTrue(self.list.head.get_next() is None)
def test_delete_value_not_in_list(self):
self.list.insert("Jacob")
self.list.insert("Pallymay")
self.list.insert("Rasmus")
with self.assertRaises(ValueError):
self.list.delete("Sunny")
def test_delete_empty_list(self):
with self.assertRaises(ValueError):
self.list.delete("Sunny")
def test_delete_next_reassignment(self):
self.list.insert("Jacob")
self.list.insert("Cid")
self.list.insert("Pallymay")
self.list.insert("Rasmus")
self.list.delete("Pallymay")
self.list.delete("Cid")
self.assertTrue(self.list.head.next_node.get_data() == "Jacob")
Source Code for creating , inserting ,deleting the Implementation of Single Linked List:
class Node(object):
def __init__(self, data, next):
self.data = data
65
self.next = next
class SingleList(object):
head = None
tail = None
def show(self):
print "Showing list data:"
current_node = self.head
while current_node is not None:
print current_node.data, " -> ",
current_node = current_node.next
print None
def append(self, data):
node = Node(data, None)
if self.head is None:
self.head = self.tail = node
else:
self.tail.next = node
self.tail = node
def remove(self, node_value):
current_node = self.head
previous_node = None
while current_node is not None:
if current_node.data == node_value:
# if this is the first node (head)
if previous_node is not None:
previous_node.next = current_node.next
else:
self.head = current_node.next
# needed for the next iteration
previous_node = current_node
current_node = current_node.next
s = SingleList()
s.append(31)
s.append(2)
66
s.append(3)
s.append(4)
s.show()
s.remove(31)
s.remove(3)
s.remove(2)
s.show()
Using a header node:
A header node is a special dummy node found at the front of the list. The use of header node is an
alternative to remove the first node in a list. For example, the picture below shows how the list with data
10, 20 and 30 would be represented using a linked list without and with a header node:
Note that if your linked lists do include a header node, there is no need for the special case code given
above for the remove operation; node n can never be the first node in the list, so there is no need to check
for that case. Similarly, having a header node can simplify the code that adds a node before a given node
n.
Note that if you do decide to use a header node, you must remember to initialize an empty list to contain
one (dummy) node, you must remember not to include the header node in the count of "real" nodes in the
list.
It is also useful when information other than that found in each node of the list is needed. For example,
imagine an application in which the number of items in a list is often calculated. In a standard linked list,
the list function to count the number of nodes has to traverse the entire list every time. However, if the
current length is maintained in a header node, that information can be obtained very quickly. 3.5. Array
based linked lists: Another alternative is to allocate the nodes in blocks. In fact, if you know the
67
maximum size of a list a head of time, you can pre-allocate the nodes in a single array. The result is a
hybrid structure – an array based linked list.
shows an example of null terminated single linked list where all the nodes are allocated contiguously in
an array.
Double Linked List: A double linked list is a two-way list in which all nodes will have two links. This
helps in accessing both successor node and predecessor node from the given node position. It provides bi-
directional traversing. Each node contains three fields:
Left link.
Data.
Right link.
The left link points to the predecessor node and the right link points to the successor node. The data field
stores the required data.
Many applications require searching forward and backward thru nodes of a list. For example searching
for a name in a telephone directory would need forward and backward scanning thru a region of the whole
list.
The basic operations in a double linked list are:
Creation.
Insertion.
Deletion.
Traversing.
A double linked list is shown in figure
68
The beginning of the double linked list is stored in a "start" pointer which points to the first node. The
first node‟s left link and last node‟s right link is set to NULL.
Creating a node for Double Linked List:
Creating a double linked list starts with creating a node. Sufficient memory has to be allocated for
creating a node. The information is stored in the memory.
Double Linked List with 3 nodes:
Inserting a node at the beginning:
Inserting a node at the end:
69
Inserting a node at an intermediate position:
Deleting a node at the beginning:
Deleting a node at the end:
Deleting a node at Intermediate position:
70
Traversal and displaying a list (Left to Right):
To display the information, you have to traverse the list, node by node from the first node, until the end
of the list is reached. The function traverse_left_right() is used for traversing and displaying the
information stored in the list from left to right.
Traversal and displaying a list (Right to Left):
To display the information from right to left, you have to traverse the list, node by node from the first
node, until the end of the list is reached. The function traverse_right_left() is used for traversing and
displaying the information stored in the list from right to left.
1.Source Code for the Implementation of Double Linked List:
class DList:
def __init__(self):
self.head = None
self.size = 0
def insert(self, data):
self.size += 1
if self.head is None:
self.head = Node(data)
else:
p = Node(data)
p.next = self.head
self.head.previous = p
self.head = p
def remove(self, index):
if self.head is None:
raise ValueError('Removing off an empty list')
if index < 0 or index >= self.size:
raise IndexError("Index is either negative or greater than the list size.")
71
current = self.head
if index == 0:
self.head = self.head.next
self.head.previous = None
else:
for _ in range(index -1):
current = current.next
p = current.next.next
if p is None:
current.next = None
else:
current.next = p
p.previous = current
def __sizeof__(self):
return self.size
def __repr__(self):
res = '[ '
current = self.head
while current is not None:
res += str(current.data)
res += ' '
current = current.next
res += ']'
return res
class Node:
def __init__(self, data):
if data is None:
raise ValueError('Node value cannot be None')
self.data = data
self.previous = None
self.next = None
Source Code for the Implementation of Double Linked List:
class Node(object):
def __init__(self, data, prev, next):
72
self.data = data
self.prev = prev
self.next = next
class DoubleList(object):
head = None
tail = None
def append(self, data):
new_node = Node(data, None, None)
if self.head is None:
self.head = self.tail = new_node
else:
new_node.prev = self.tail
new_node.next = None
self.tail.next = new_node
self.tail = new_node
def remove(self, node_value):
current_node = self.head
while current_node is not None:
if current_node.data == node_value:
# if it's not the first element
if current_node.prev is not None:
current_node.prev.next = current_node.next
current_node.next.prev = current_node.prev
else:
# otherwise we have no prev (it's None), head is the next one, and prev becomes None
self.head = current_node.next
current_node.next.prev = None
current_node = current_node.next
def show(self):
print "Show list data:"
current_node = self.head
73
while current_node is not None:
print current_node.prev.data if hasattr(current_node.prev, "data") else None,
print current_node.data,
print current_node.next.data if hasattr(current_node.next, "data") else None
current_node = current_node.next
print "*"*50
d = DoubleList()
d.append(5)
d.append(6)
d.append(50)
d.append(30)
d.show()
d.remove(50)
d.remove(5)
d.show()
Circular Single Linked List:
It is just a single linked list in which the link field of the last node points back to the address of the first
node. A circular linked list has no beginning and no end. It is necessary to establish a special pointer
called start pointer always pointing to the first node of the list. Circular linked lists are frequently used
instead of ordinary linked list because many operations are much easier to implement. In circular linked
list no null pointers are used, hence all pointers contain valid address.
Creating a circular single Linked List with „n‟ number of nodes:
The basic operations in a circular single linked list are:
• Creation.
• Insertion.
• Deletion.
• Traversing.
74
Inserting a node at the beginning:
Inserting a node at the end:
Deleting a node at the beginning:
Deleting a node at the end:
Source Code for Circular Single Linked List:
75
from enum import Enum
class NodeConstants(Enum):
FRONT_NODE = 1
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
def __str__(self):
if self.element:
return self.element.__str__()
else:
return 'Empty Node'
def __repr__(self):
return self.__str__()
class CircularLinkedList:
def __init__(self):
self.head = Node(element=NodeConstants.FRONT_NODE)
self.head.next_node = self.head
def size(self):
count = 0
current = self.head.next_node
while current != self.head:
count += 1
current = current.next_node
return count
def insert_front(self, data):
node = Node(element=data, next_node=self.head.next_node)
self.head.next_node = node
def insert_last(self, data):
current_node = self.head.next_node
while current_node.next_node != self.head:
current_node = current_node.next_node
node = Node(element=data, next_node=current_node.next_node)
current_node.next_node = node
def insert(self, data, position):
76
if position == 0:
self.insert_front(data)
elif position == self.size():
self.insert_last(data)
else:
if 0 < position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position - 1:
current_pos += 1
current_node = current_node.next_node
node = Node(data, current_node.next_node)
current_node.next_node = node
else:
raise IndexError
def remove_first(self):
self.head.next_node = self.head.next_node.next_node
def remove_last(self):
current_node = self.head.next_node
while current_node.next_node.next_node != self.head:
current_node = current_node.next_node
current_node.next_node = self.head
def remove(self, position):
if position == 0:
self.remove_first()
elif position == self.size():
self.remove_last()
else:
if 0 < position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position - 1:
current_node = current_node.next_node
current_pos += 1
current_node.next_node = current_node.next_node.next_node
77
else:
raise IndexError
def fetch(self, position):
if 0 <= position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position:
current_node = current_node.next_node
current_pos += 1
return current_node.element
else:
raise IndexError
import unittest
from random import randint
class TestCircularLinkedList(unittest.TestCase):
names = ['Bob Belcher',
'Linda Belcher',
'Tina Belcher',
'Gene Belcher',
'Louise Belcher']
def test_init(self):
dll = CircularLinkedList()
self.assertIsNotNone(dll.head)
self.assertEqual(dll.size(), 0)
def test_insert_front(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_front(name)
self.assertEqual(dll.fetch(0), TestCircularLinkedList.names[4])
self.assertEqual(dll.fetch(1), TestCircularLinkedList.names[3])
self.assertEqual(dll.fetch(2), TestCircularLinkedList.names[2])
self.assertEqual(dll.fetch(3), TestCircularLinkedList.names[1])
self.assertEqual(dll.fetch(4), TestCircularLinkedList.names[0])
def test_insert_last(self):
78
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
for i in range(len(TestCircularLinkedList.names) - 1):
self.assertEqual(dll.fetch(i), TestCircularLinkedList.names[i])
def test_insert(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
pos = randint(0, len(TestCircularLinkedList.names) - 1)
dll.insert('Teddy', pos)
self.assertEqual(dll.fetch(pos), 'Teddy')
def test_remove_first(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
for i in range(dll.size(), 0, -1):
self.assertEqual(dll.size(), i)
dll.remove_first()
def test_remove_last(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
for i in range(dll.size(), 0, -1):
self.assertEqual(dll.size(), i)
dll.remove_last()
def test_remove(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
dll.remove(1)
self.assertEqual(dll.fetch(0), 'Bob Belcher')
self.assertEqual(dll.fetch(1), 'Tina Belcher')
self.assertEqual(dll.fetch(2), 'Gene Belcher')
self.assertEqual(dll.fetch(3), 'Louise Belcher')
79
if __name__ == '__main__':
unittest.main()
Circular Double Linked List:
A circular double linked list has both successor pointer and predecessor pointer in circular manner. The
objective behind considering circular double linked list is to simplify the insertion and deletion operations
performed on double linked list. In circular double linked list the right link of the right most node points
back to the start node and left link of the first node points to the last node.
A circular double linked list is shown in figure
Creating a Circular Double Linked List with „n‟ number of nodes
The basic operations in a circular double linked list are:
• Creation.
• Insertion.
• Deletion.
• Traversing.
Inserting a node at the beginning:
Inserting a node at the end:
80
Inserting a node at an intermediate position:
Deleting a node at the beginning:
Deleting a node at the end:
81
Deleting a node at Intermediate position:
Comparison of Linked List Variations:
The major disadvantage of doubly linked lists (over singly linked lists) is that they require more space
(every node has two pointer fields instead of one). Also, the code to manipulate doubly linked lists needs
to maintain the prev fields as well as the next fields; the more fields that have to be maintained, the more
chance there is for errors.
The major advantage of doubly linked lists is that they make some operations (like the removal of a given
node, or a right-to-left traversal of the list) more efficient.
The major advantage of circular lists (over non-circular lists) is that they eliminate some extra-case code
for some operations (like deleting last node). Also, some applications lead naturally to circular list
representations. For example, a computer network might best be modeled using a circular list.
Polynomials:
A polynomial is of the form: i n i ∑ ci
Where, ci is the coefficient of the ith term and
n is the degree of the polynomial
Some examples are:
5x2 + 3x + 1
12x3 – 4x
5x4 – 8x3 + 2x2 + 4x1 + 9x0
82
It is not necessary to write terms of the polynomials in decreasing order of degree. In other words the two
polynomials 1 + x and x + 1 are equivalent.
The computer implementation requires implementing polynomials as a list of pairs of coefficient and
exponent. Each of these pairs will constitute a structure, so a polynomial will be represented as a list of
structures.
A linked list structure that represents polynomials 5x4 – 8x3 + 2x2 + 4x1 + 9x0
Addition of Polynomials:
To add two polynomials we need to scan them once. If we find terms with the same exponent in the two
polynomials, then we add the coefficients; otherwise, we copy the term of larger exponent into the sum
and go on. When we reach at the end of one of the polynomial, then remaining part of the other is copied
into the sum.
To add two polynomials follow the following steps:
• Read two polynomials
• Add them.
• Display the resultant polynomial.
83
