Project – Linked List

Implementing Python-style Lists in C

Lists are one of the most important built-in data types in the Python Programming Language. The standard Python implementation is written in C and the core list data type is also implemented in C. For this project you will implement Python-style lists in  C.

Due Date: Monday November 26th, at 11:59pm

Overview of Python Lists

In Python, lists can contain an arbitrary number of elements. For example:

>>> l1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> print l1

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> l2 = [99, 199, 299, 400]

>>> print l2

[99, 199, 299, 400]

Lists  can  contain  different  types of data. In the example above, l1 and l2 contain integers, below, we see lists of strings and doubles:

l3 = [“a”, “b”, “c”, “d”]

>>> print l3 [‘a’, ‘b’, ‘c’, ‘d’]

>>> l4 = [1.8, 2.7, 1.2, 4.7, 3.3]

>>> print l4

[1.8, 2.7000000000000002, 1.2, 4.7000000000000002, 3.2999999999999998]

In Python, lists can contain elements with different data types: l5 = [‘apple’, 2, 3, ‘pear’, 3.1, 3.7]

>>> print l5

[‘apple’, 2, 3, ‘pear’, 3.1000000000000001, 3.7000000000000002]

In fact, in Python, lists can also contain other lists: l6 = [[1,2,3], [4,5,6], [7,8,7]]

>>> print l6

[[1, 2, 3], [4, 5, 6], [7, 8, 7]]

>>> l7 = [[“CA”, [“San Francisco”, “Sacramento”, “Los Angeles”]], [“UT”, [“Salt Lake

City”, “Moab”]], [“OR”, [“Portland”, “Bend”]]]

>>> print l7

[[‘CA’, [‘San Francisco’, ‘Sacramento’, ‘Los Angeles’]], [‘UT’, [‘Salt Lake City’, ‘Moab’]], [‘OR’, [‘Portland’, ‘Bend’]]]

In Python you can perform a variety of operations on lists. You can select elements using an index:

>>> print l7[1][1] [‘Salt Lake City’, ‘Moab’]

>>> print l7[1][1][0] Salt Lake City

>>>

You can modify an element using an index:

>>> l8 = [3.0, 4.0, 5.1, 6.2]

>>> print l8

[3.0, 4.0, 5.0999999999999996, 6.2000000000000002]

>>> l8[3] = 5.9

>>> print l8

[3.0, 4.0, 5.0999999999999996, 5.9000000000000004]

>>>

You can append to a list:

>>> l1 = [1, 2, 3]

>>> print l1 [1, 2, 3]

>>> l1.append(4)

>>> print l1 [1, 2, 3, 4]

You can determine the length of a list:

>>> len(l1) 4

You can insert into a list: l1.insert(0, 0)

>>> print l1

[0, 1, 2, 3, 4]

You delete a list:

>>> del l1

A C Implementation of Python Lists

For this project you will implement a subset of the Python list data type and operations.

High-level Functions

You will also implement some high-level list operations:

● min

● max

● concat

● reverse

● sort