Page 4 - DATA STRUCTURE-LISTS

Implementation of List in Memory

In any programming language, an array is defined as a set of contiguous data of similar data
type. Arrays can be static/fixed size or dynamic/variable size.

Python lists are actually arrays of variable length. The elements of a list are of
heterogeneous types which means they are of different data types. Hence

[4,"Good", 8.45, 'k'] is a valid list.

This is possible because in Python language, technically pointers (not objects) are stored in
the form of an array. So a list in Python is an array that contains elements (pointers to
objects) of a specific size only and this is a common feature of all dynamically typed
languages.

For implementation of a list, a contiguous array of references to other objects is used.
Python keeps a pointer to this array and the array's length is stored in a list head structure.
This makes indexing of a list independent of the size of the list or the value of the index.
When items are appended or inserted, the array of references is resized.

List operations in Data Structure

1. Traversal
2. Insertion
3. Deletion
4. Modification
5. Sorting
6. Merging

List Traversal

(visiting each element atleast once)
def Traversal(L):
for i in range len(L):
print(L[i])
X=[11, 22, 33, 44, 55]
Traversal(X)

Insertion
Can be:
 At the end of the list
 In a sorted list
Insertion at the end:
X=[11, 33, 55, 77, 88, 99]
a=int(input("Enter element to insert: "))
X.append(a)
print(X)

Insertion in a sorted list