The arrangement of data within the memory forms the basis of computing. The arrangement of data is known as data-structure. Every language provides variety of built-in data-structures. Languages such as C provide basic data-structure mechanisms using which complex structures can be built whereas languages such as Java use full-blown object-oriented approach for almost all types of data-structures. Then there are languages like Python which takes a middle approach. In this article I would be discussing the middle path used by Python using two of its built-in data-structures – Lists and Tuples. The first section would focus on functionalities of Lists and Tuples. In the second section I would develop a real world application which makes use of Lists and/or Tuples. That’s the agenda for this discussion.

 

List and Tuple – More About Them:

List and Tuple are two of the basic built-in data-structures. As with all other features of Python, these in-built data-structures provide both flexibility and power. The answer to how flexible and powerful they are is what I am going to discuss now. First lets look at List data-structure.

 

1. List:

By definition a List is “An instance of an abstract data type (ADT), formalizing the concept of an ordered collection of entities”. In other words, a List is a collection of objects. In contrast with Array, List contains different objects. That’s how Python also views Lists. Data types (that’s what Python calls built-in data-structures too) such as List is known as compound data type in Python. The operations that can be performed on a List are:

 

a. Creation

b. Addition of elements

c. Accessing and Searching

d. Deletion

 

Many of the library functions essentially create Lists. These functions may be working on Lists themselves such as during accessing and searching. Here are the details:

 

a. Creation:

A List is defined as list of coma separated values between square brackets thus:

 

a = ['spam', 'eggs', 100, 1234]

 

where the items of the List a are of different data types.  This is the most common method of creating a list. The other technique is to use the range() function. The range() function provides a List of consecutive integers. The range() function takes two arguments. The List returned contains all the integers from the first to the second, including the first but not including the second. For example,

>>range(1, 5)

Gives

[1,2,3,4]

Since List itself is a data type, so a List can contain another List. For example,

 

[1,”a”,[2,3]]

 

is perfectly valid List.

 

b. Addition of elements:

There are three ways to add elements to an existing List using member functions of the List which are:

 

i. append adds a single element to the end of the List. For example, let li be

a List, then

>>> li

['a', 'b', 'mpilgrim', 'z', 'example']

>>> li.append(“new”)

>>> li

['a', 'b', 'mpilgrim', 'z', 'example', 'new']

 

ii. insert method inserts a single element into the List. The numeric argument

is the index of the first element that gets shifted out of position. Also there can be two elements of same value at two different positions.

 

>>> li.insert(2, “new”)

>>> li

['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new']

iii. extends concatenates the List passed as argument with the existing List.

For example,

>>> li.extend(["two", "elements"])

>>> li

['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']

 

c. Accessing and Searching:

For accessing and searching, one of the following techniques can be used:

 

i. Slicing:

Slice is a sub-list of a List. Slicing is done using the [n : m] which

returns the part of the List from the n-eth character to the m-eth

character, including the first but excluding the last. For example if a_list is

a List of alphabets from a to f, then

 

>>> a_list = ['a', 'b', 'c', 'd', 'e', 'f']

>>> a_list[1:3]

['b', 'c']

>>> a_list[:4]

['a', 'b', 'c', 'd']

>>> a_list[3:]

['d', 'e', 'f']

>>> a_list[:]

['a', 'b', 'c', 'd', 'e', 'f']

 

ii. Indexing:

Index of a given element can be found using the index() function of List. It returns the first occurrence of the element supplied as argument. That means even if the element occurs twice, only the position of the first element would be returned. If  the element is not found an exception is raised. For example

>>>li=['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']

>>> li

['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']

>>> li.index(“example”)

5

>>> li.index(“new”)

2

>>> li.index(“c”)

Traceback (innermost last):

File “<interactive input>”, line 1, in ?

ValueError: list.index(x): x not in list

 

Apart from these, a List can be accessed as one access an array by specifying index thus:

>>>li=['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']

>>>li[0]

‘a’

d. Deletion:

To delete an element from a List, one can us del. It removes an element from the specified List. For example:

>>> a = ['one', 'two', 'three']

>>> del a[1]

>>> a

['one', 'three']

 

del also can have slice thus:

>>> a_list = ['a', 'b', 'c', 'd', 'e', 'f']

>>> del a_list[1:5]

>>> print a_list

['a', 'f']

That’s all about the operations on Lists. The way the operations are implemented shows the flexibility of Python’s middle path approach. The flexibility doesn’t just stop here. Though strings are immutable and Lists are mutable yet they are inter-convertible. Two of the most useful functions in the string module involve Lists of strings – split and join. The former returns a List composed of individual elements of string separated by the delimiter passed as argument. While the latter creates a string out of supplied List. Following are the examples:

 

>>> import string

>>> song = “The rain in Spain…”

>>> string.split(song)

['The', 'rain', 'in', 'Spain...']

 

Here the string is split on the basis of space as delimiter which is the default delimiter. Next example shows the reverse of the above functionality – string from a List:

 

>>> lst = ['The', 'rain', 'in', 'Spain...']

>>> string.join(lst)

‘The rain in Spain…’

where the joining is done on the basis of space delimiter which again is default delimiter. That’s all about Lists at present. Next lets look at the other compound data-type – Tuple.

 

2. Tuple:

According to definition, “A tuple is a finite sequence (also known as an “ordered list”) of objects, each of a specified type”. In other words, a Tuple is an ordered collection of  objects of different types. In Python, a Tuple is a list of comma separated values but immutable unlike List. So the operations on a Tuple are restricted to the ones that don’t affect its immutability. Accordingly following are the operations that can be performed on a Tuple are:

 

a. Creation

b. Accessing

 

Due to immutability, deletion and addition of new elements are not possible.

 

a. Creation:

Creating or defining a Tuple is as simple as giving a list of values within parenthesis. For example

 

>>> tup = (2, 4, 6, 8, 10)

 

is a Tuple. If a Tuple is having only one element, then, it would be defined as follows:

>>> tup = (5,)

 

b. Accessing:

Since Lists and Tuples are almost same, so the accessing mechanisms also works in similar fashion. Elements of a Tuple can be accessed in two ways:

 

i. Index based:

The elements of a  Tuple can be accessed using their indices. The

index starts at 0. For example to access an element at index 0 of a Tuple

tup, the statement would be:

 

>>> tup = (‘a’, ‘b’, ‘c’, ‘d’, ‘e’)

>>> tup[0]

‘a’

 

ii. Slicing:

As in List, slice operator can be used to access elements of a Tuple. It selects a range of elements. For example the following statement selects elements between 1 and 3 (excluding 3):

>>> tup[1:3]

(‘b’, ‘c’)

That’s about operations on a Tuple. So the question arises, when to use List and when to use Tuple. List can be used almost in all the cases. However, there are certain contexts where Tuple is more useful which are:

 

  • Tuples are faster than lists. If you’re defining a constant set of values and all you’re ever going to do with it is iterate through it, use a tuple instead of a list.
  • It makes your code safer if you “write-protect” data that does not need to be changed. Using a Tuple instead of a list is like having an implied assert statement that this data is constant, and that special thought (and a specific function) is required to override that.

 

In all other contexts, Lists can be used. That brings us to the next section – a real world example using List.

 

Lists And Tuples – In Real World:

The example application would implement a ring buffer or a bounded buffer using List. In a bounded buffer, once the capacity is full, then the first element i.e. the oldest element is replaced with newest element. The implementation uses class switch pattern. Here is the code:

 

class RingBuffer(object):

“”” class that implements a not-yet-full buffer “””

def __init__(self, size_max):

self.max = size_max

self.data = [  ]

class __Full(object):

“”” class that implements a full buffer “””

def append(self, x):

“”” Append an element overwriting the oldest one. “””

self.data[self.cur] = x

self.cur = (self.cur+1) % self.max

def tolist(self):

“”” return list of elements in correct order. “””

return self.data[self.cur:] + self.data[:self.cur]

def append(self, x):

“”” append an element at the end of the buffer. “””

self.data.append(x)

if len(self.data) == self.max:

self.cur = 0

# Permanently change self’s class from non-full to full

self.__class__ = __Full

def tolist(self):

“”” Return a list of elements from the oldest to the newest. “””

return self.data

The class defines an empty List as a buffer. The nested class __Full implements the logic to overwrite the oldest element if the buffer is full. The tolist method returns the List in correct order. Next the append method of the outer class i.e. RingBuffer appends a new item to the end of the List. It also checks whether the length of the buffer is equal to  the max size. If it is equal, then buffer’s state is changed to full. The tolist method returns the buffer. Following is sample implementation that shows how to use the RingBuffer class:

 

if __name__ == ‘__main__’:

x = RingBuffer(5)

x.append(1); x.append(2); x.append(3); x.append(4)

print x.__class__, x.tolist( )

x.append(5)

print x.__class__, x.tolist( )

x.append(6)

print x.data, x.tolist( )

x.append(7); x.append(8); x.append(9); x.append(10)

print x.data, x.tolist( )

That brings us to the end of this discussion. List and Tuple are the basic data-structures found in Python. On the basis of these more complex structures such as trees can be developed. How to implement them would be the topic for discussion in the future. Till then…

About these ads