Storing and manipulating lists of information is a fundamental part of computing.Programming environments facilitate list processing by providing list constructs as either a built-in part of the language or as library classes.
Python has high-level lists built directly into the language. Here are some of the key methods, many of which you have used:
| len | len(list) | | append | list.append(item) | | set/get | list[i]=4, print list[i] | | sort | list.sort() | | range | list[2:7]
| | in | if item in list:
for item in list:
|
Java provides built-in lists called arrays which have less functionality (e.g., no append). Java provides higher-level functionality in its library with LinkedList, ArrayList and other Collection classes.
In this lesson, we'll look beneath the hood at how these list constructs are implemented.
In real-life, you will probably never need to write code for a list class, or for the basic list operations. But it is still instructive to learn how this code works and to discuss issues such as how efficiently the basic operations can be implemented using various schemes. It is part of the basics-- the kind of stuff an interviewer at Google might ask you to code on a whiteboard.
List Implementation
There are two basic strategies for implementing a list:
- Allocate a big chunk of contiguous memory cells for the list to begin (we'll call this an ArrayList)
- Allocate each memory cell for the list on an as-needed basis, and link the memory cells together (we'll call this a LinkedList)
ArrayLists
ArrayLists store elements in contiguous memory:
Array data structures must keep track of the size of the chunk of memory allocated and the number of elements actually stored in it.
Let's suppose that the Python list structure is dumber than it really is, and that it is more like Java's built-in arrays and doesn't have any high-level functions like append. We could build a ArrayList class that would wrap the built-in list:
class ArrayList:
def __init__(self):
self.list=[0]*100 # initialize with 0s in each cell
self.numElements=0 # the number of things put in
def append(self, item):
# need to check if the internal list has enough items
# if things are ok, put the element in...
self.list[self.numElements]=item
self.numElements=self.numElements+1
In the constructor, we initialize the elements in the ArrayList to 0 and give the ArrayList an initial size of 100.
Linked lists
are an alternative way to implement a list data structure. Linked lists do not
store elements contiguously, but instead link each element to the next
with a pointer (address).
To implement a LinkedList, we define two classes. One class holds each element and a special 'next' pointer linking to the next element in the list:
class Element:
def __init__(self,x):
self.data=x
# maybe some more data
self.next=None # null
The List class then just keeps a pointer to the head and tail of the list:
class LinkedList:
def __init__(self):
head=None
tail=None
def append(self,item)
# link new node into end of list
Appending to an ArrayList and a LinkedList
Our list classes should provide high-level functions to make list processing easy. Let's first consider an 'append' function. Suppose we want to be able to create a list with:
list = LinkedList() # or list=ArrayList()
list.append("Joe")
list.append("Bill")
1. Draw a picture of what memory would look like after the two elements were appended to an ArrayList.
2. Draw a picture of what memory would look like after the two elements were appended to an LinkedList.
3. Sketch out the code for an append function for ArrayList.
4. Sketch out the code for an append function for LinkedList.
5. What if we were to append 101 elements to an ArrayList. Would your code still work? How would you fix the code?
6. What if were to append 101 elements to a LinkedList. Would your code still work?
7. What is the worst-case efficiency (Big-0) of the append function for ArrayList? For LinkedList?
8. Using what you've learned from this discussion, Implement an ArrayList class with data as described above. For now, provide only an append function, the __init__ function, and a __str__ function. Your main program should just insert three strings into the list, then call print on the list.
9. Now implement a LinkedList class with the same functions.
|
Attachments (1)
-
linkedlist.py - on Nov 24, 2008 12:15 PM by David Wolber (version 1)
1k
Download
|
