Data structures and algorithm

CD3291-DATA STRUCTURES AND ALGORITHMS

UNIT II LINEAR STRUCTURES
List ADT – array-based implementations – linked list implementations – singly linked lists –
circularly linked lists – doubly linked lists – Stack ADT – Queue ADT – double ended queues –
applications


LIST ADT:
Lists are used to store multiple items in a single variable. Lists are one of 4 built-in data
types in Python used to store collections of data, the other 3 are Tuple, Set, and Dictionary, all
with different qualities and usage. Lists are created using square brackets.Python Lists are just
like dynamically sized arrays, declared in other languages, In simple language, a list is a
collection of things, enclosed in [ ] and separated by commas.

Creating a List in Python
Lists in Python can be created by just placing the sequence inside the square brackets[ ].
Example:
List = [ ]
print("Blank List: ")
print(List)
# Creating a List of numbers
List = [10, 20, 14]
print("\nList of numbers: ")
print(List)
OUTPUT:
Blank List:
[]
List of numbers:
[10, 20, 14]

Creating a list with multiple distinct or duplicate elements
A list may contain duplicate values with their distinct positions and hence, multiple distinct or
duplicate values can be passed as a sequence at the time of list creation.
Example :
List = [1, 2, 4, 4, 3, 3, 3, 6, 5]
print("\nList with the use of Numbers: ")
print(List)
# Creating a List with mixed type of values (Having numbers and strings)
List = [1, 2, 'Apple', 4, 'For', 6, 'Orange']
print("\n List with the use of Mixed Values: ")

, CD3291-DATA STRUCTURES AND ALGORITHMS

print(List)

Output
List with the use of Numbers:
[1, 2, 4, 4, 3, 3, 3, 6, 5]
List with the use of Mixed Values:
[1, 2, 'Apple', 4, 'For', 6, 'Orange']

Accessing elements from list
In order to access the list items refer to the index number. Use the index operator [ ] to access an
item in a list. The index must be an integer.
Example :
# accessing of element from list
# Creating a List with the use of multiple values
List = ["Geeks", "For", "Geeks"]
# accessing a element from the list using index number
print("Accessing a element from the list")
print(List[0])
print(List[2])
Output
Accessing a element from the list
Apple
Mango

Accessing elements from a multi-dimensional list
# Creating a Multi-Dimensional List (By Nesting a list inside a List)
List = [['hi', 'how'], ['you']]
# accessing an element from the Multi-Dimensional List using index number
print("Accessing a element from a Multi-Dimensional list")
print(List[0][1])
print(List[1][0])
Output

, CD3291-DATA STRUCTURES AND ALGORITHMS

Accessing a element from a Multi-Dimensional list

how
you

Negative indexing
In Python, negative sequence indexes represent positions from the end of the array. Instead of
having to compute the offset as in List[len(List)-3], it is enough to just write List[-3]. Negative
indexing means beginning from the end, -1 refers to the last item, -2 refers to the second-last
item, etc.
List = [1, 2, 'Apple', 4, 'Mango', 6, 'Orange']
# accessing an element using negative indexing
print("Accessing element using negative indexing")
# print the last element of list
print(List[-1])
# print the third last element of list
print(List[-3])
OUTPUT:
Accessing element using negative indexing
Orange
Mango

Finding Length of the List
Python len() is used to get the length of the list.
# Creating a List
List1 = []
print(len(List1))
# Creating a List of numbers
List2 = [10, 20, 14]
print(len(List2))
OUTPUT:
0
3

Adding Elements to a Python List

Method 1: Using append () method
Elements can be added to the List by using the built-in append() function. Only one element at
a time can be added to the list by using the append () method, for the addition of multiple
elements with the append () method, loops are used. Tuples can also be added to the list with

, CD3291-DATA STRUCTURES AND ALGORITHMS

the use of the append method because tuples are immutable. Unlike Sets, Lists can also be
added to the existing list with the use of the append () method.

Method 2: Using insert () method
append() method only works for the addition of elements at the end of the List, for the addition
of elements at the desired position, insert() method is used. Unlike append () which takes only
one argument, the insert () method requires two arguments (position, value).
# Python program to demonstrate Addition of elements in a List
# Creating a List
List = [1,2,3,4]
print("Initial List: ")
print(List)
# Addition of Element at specific Position (using Insert Method)
List.insert(3, 12)
List.insert(0, 'Apple')
print("\nList after performing Insert Operation: ")
print(List)
OUTPUT:
Initial List:
[1, 2, 3, 4]
List after performing Insert Operation:
['Apple', 1, 2, 3, 12, 4]

Method 3: Using extend() method
Other than append() and insert() methods, there’s one more method for the Addition of
elements, extend(), this method is used to add multiple elements at the same time at the end of
the list.
# Creating a List
List = [1, 2, 3, 4]
print("Initial List: ")
print(List)
# Addition of multiple elements to the List at the end (using Extend Method)
List.extend([8, 'Apple', 'Always'])
print("\nList after performing Extend Operation: ")
print(List)
OUTPUT:
Initial List:
[1, 2, 3, 4]
List after performing Extend Operation: