1
CMPSC-132: Programming and Computation II
Department of Computer Science & Engineering
The Pennsylvania State University
1. Data Structures
A data structure is a particular way of organizing data in a computer so that it can be used effectively.
The idea is to reduce the space and time complexities of different tasks. Below is an overview of some
popular linear data structures.
1.1 Linked List
Python’s list class is highly optimized, and often a great choice for storage. With that said, there are
some notable disadvantages:
• The length of a dynamic array might be longer than the actual number of elements that it stores.
• Amortized bounds for operations may be unacceptable in real-time systems.
• Insertions and deletions at interior positions of an array are expensive.
Linked lists provide an alternative to an array-based sequence (such as a Python list). Both array-based
sequences and linked lists keep elements in a certain order, but using a very different style. An array
provides the more centralized representation, with one large chunk of memory capable of accommodating
references to many elements. A linked list, in contrast, relies on a more distributed representation in which
a lightweight object, known as a node, is allocated for each element. Each node maintains a reference to
its element and one or more references to neighboring nodes in order to collectively represent the linear
order of the sequence. Unlike array-based sequences, linked list elements are not stored at contiguous
location; the elements are linked using pointers.
Linked list is often compared to array-based sequences. Whereas an array is a fixed size of sequence, a
linked list can have its elements to be dynamically allocated. Eventually, it comes with its pros and cons:
• PRO: A linked list saves memory since it only allocates the memory required for values to be stored.
In arrays, you have to set an array size before filling it with values, which can potentially waste
memory.
• PRO: Linked list nodes can live anywhere in the memory. Whereas an array requires a sequence of
memory to be initiated, as long as the references are updated, each linked list node can be flexibly
moved to a different address.
2 4 6 8
value next (pointer)
Head
Tail
NULL
2
• CON: Linked lists have linear look up time. When looking for a value in a linked list, you have to
start from the beginning of the chain, and check one element at a time for a value you are looking
for. If the linked list is n elements long, this can take up to n time.
Below is the basic structure of a linked list in Python:
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
Implementation of a linked list with 4 nodes:
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def printList(self):
temp = self.head
while (temp):
print(temp.value, end=’ ‘)
temp = temp.next
if __name__==’__main__’:
linked_list = LinkedList()
linked_list.head = Node(2)
node2 = Node(4)
node3 = Node(6)
node4 = Node(8)
linked_list.head.next = node2
node2.next = node3
node3.next = node4
linked_list.printList()
Initializing node object:
– Value assignments
– Initialize next as NULL
Initializing linked list object:
– Initialize head of list as NULL
printList() traverses the created list and prints
the data of each node.
Creating the 4 nodes:
2 4 6 8
Linking nodes:
2 4 6 8 NULL
3
1.1.1 Inserting nodes
A node can be added to a linked list in three ways: (i) at the front of the linked list, (ii) after a given
node or (iii) at the end of the linked list:
class LinkedList:
def __init__(self):
self.head = None
def add_first(self, e):
new_node = Node(e)
new_node.next = self.head
self.head = new_node
class LinkedList:
def __init__(self):
self.head = None
def add_last(self, e):
new_node = Node(e)
new_node.next = None
if self.head is None:
self.head = new_node
return
last = self.head
while (last.next):
last = last.next
last.next = new_node
2 4 6 8 NULL
1
Head
create new node instance storing reference to element e
set new node’s next to reference the old head node
set variable head to reference the new node
2 4 6 8 NULL
1 NULL temp = 8
create new node instance storing reference to element e
set new node’s next to reference the None object
if the linked list is empty, then make the new_node as head
traverse list until the last node is reached, then change
the next of last node to new_node
4
1.1.2 Deleting nodes
To delete a node from linked list, we need to do following steps:
• Find previous node of the node to be deleted
• Changed next of previous node
• Free memory for the node to be deleted (for C/C++)
class LinkedList:
def __init__(self):
self.head = None
def delete_first(self):
if self.head is None:
print(“The list is empty”)
return
self.head = self.head.next
Unfortunately, we cannot easily delete a given node or the last node of a singly linked list. Even if we
maintain a tail reference directly to the last node of the list, we must be able to access the node before the
last node in order to remove the last node. But we cannot reach the node before the tail by following next
links from the tail. The only way to access this node is to start from the head of the list and search all the
way through the list. But such a sequence of link-hopping operations could take a long time. If you want to
support such an operation efficiently, you will need to make your list doubly linked.
class LinkedList:
def __init__(self):
self.head = None
def delete_node(self, e):
temp = self.head
if (temp is not None):
if (temp.value == e):
self.head = temp.next
temp = None
return
2 4 6 8 NULL
Head Head
make head point to next node (or None)
2 4 6 8 NULL
prev = 4
temp = 6
temp store the current head node
if the head node itself holds the value to be deleted, make
head point to next node and point temp to None
5
while(temp is not None):
if temp.value == e:
break
prev = temp
temp = temp.next
if(temp == None):
return
prev.next = temp.next
temp = None
1.1.3 Circular Linked List
A circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL
at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.
Some of the advantages of circular linked lists are:
• Any node can be a starting point. You can traverse the whole list by starting from any point. You
just need to stop when the first visited node is visited again.
• Useful for implementation of queues. You do not need to maintain two pointers for front and rear
if we use circular linked list. You can maintain a pointer to the last inserted node and front can
always be obtained as next of last.
• Circular lists are useful in applications to repeatedly go around the list.
In a conventional linked list, you traverse the list from the head node and stop the traversal when you reach
NULL. In a circular linked list, you stop traversal when we reach the first node again.
class Node:
def __init__(self, value):
self.value = value
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def add_first(self, e):
new_node = Node(e)
temp = self.head
new_node.next = self.head
traverse the list looking for the value to be deleted, keeping
track of the previous node since we need to change the
node.next value
key was not present in linked list
unlinking the node from linked list
2 4 6 8
Head
inserting a node at the beginning of the list:
– create a new_node
– make new_node.next = last_node.next
– make last_next = new_node
–
6
if self.head is not None:
while(temp.next != self.head):
temp = temp.next
temp.next = new_node
else:
new_node.next = new_node
self.head = new_node
def printList(self):
temp = self.head
if self.head is not None:
while (temp):
print(temp.value, end=’ ‘)
temp = temp.next
if (temp == self.head):
break
if __name__==’__main__’:
circular_list = CircularLinkedList()
circular_list.add_first(8)
circular_list.add_first(6)
circular_list.add_first(4)
circular_list.add_first(2)
circular_list.printList() # 2 4 6 8
1.1.4 Doubly Linked List
A doubly linked list (DLL) contains an extra pointer, typically called previous pointer, together with
next pointer and data which are there in singly linked list.
Some of the advantages of doubly linked lists over singly linked lists are:
• A doubly linked list can be traversed in both forward and backward direction.
• The delete operation in doubly linked list is more efficient if pointer to the node to be deleted is
given. Remember that in singly linked list, to delete a node, pointer to the previous node is needed.
To get this previous node, sometimes the list is traversed. In doubly linked list, we can get the
previous node using previous pointer.
Some of the disadvantages of doubly linked lists over singly linked lists are:
• Every node of doubly linked list requires extra space for a previous pointer.
• All operations require an extra pointer previous to be maintained. For example, in insertion, we
need to modify previous pointers together with next pointers.
Only for the first node
2 4 6 8 NULL NULL
Head
7
A node can be added to a doubly linked list in four ways: (i) at the front of the list, (ii) after a given node,
(iii) at the end of the list, (iv) before a given node.
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def add_first(self, e):
new_node = Node(e)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
1.2 Stack
A stack is a linear data structure with three basic operations:
• Push: Adds an element on top of the stack. If the stack is full, then it is said to be an Overflow
condition.
• Pop: Removes an element from the stack. The items are popped in the reversed order in which they
are pushed. If the stack is empty, then it is said to be an Underflow condition.
• isEmpty: Returns true if stack is empty, else false.
One extra method available to a stack is the ability to “peek”. This method returns the top element of the
stack without removing it. In a stack, elements are inserted and removed according to the LIFO (Last In,
First Out) or FILO (First In, Last Out) principle. A user may insert objects into a stack at any time, but may
only access or remove the most recently inserted object that remains (at the so-called “top” of the stack).
2 4 6 8 NULL NULL
Head
1 NULL
Head
Make next of new_node the head and previous as
None (already None in the Node class)
change previous of head node to the new_node
head points to the new_node
8
Stacks are useful to trace back previous elements/operations. For example, undo operations in editors are
like popping a code change that was just pushed in the stack of edit history, or back operations in browsers
are like popping a site visit that was just pushed in the stack of browser history. Stacks also come in handy
when matching recursive elements/operation. For example, balancing of symbols, tree traversals, or the
recursive algorithm to implement the Towers of Hanoi. Stacks can be implemented using array-based
sequences or linked lists. The code below shows a linked list implementation of a stack:
class StackNode:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
def __init__(self):
self.stack = None
def is_empty(self):
return True if self.stack is None else False
def push(self,e):
newNode = StackNode(e)
newNode.next = self.stack
self.stack = newNode
print(“%d pushed in stack” %e)
Although this implementation can grow and shrink according to the runtime needs, it requires extra memory
due to the use of pointers.
Stack is empty when the root of the list is empty
9
1.3 Queue
Another fundamental data structure is the queue. Like stacks, queues are a linear structure which
follows a particular order in which the operations are performed. In a queue, its elements are inserted and
removed according to the FIFO (First In, First Out) or LILO (Last In, Last Out) principle. A queue has two
basic operations:
• Enqueue: append an element to the tail of the queue
• Dequeue: remove an element from the head of the queue
One extra method available to a queue is to now who is at the head of the queue. This method returns a
reference to the element at the front of queue without removing it.
Queues are used whenever you want to process things one at a time as they come in. Some examples are,
uploading bunch of images, printing multiple documents, and processing thousands of requests to a web
server. Queues can also be implemented using array-based sequences or linked lists. The code below shows
an array-based implementation of a queue:
class Queue:
def __init__(self):
self.queue = []
def enqueue(self,val):
self.queue.append(val)
def dequeue(self):
if self.is_empty():
return None
else:
return self.queue.pop(0)
1.3.1 Priority Queues
Priority Queue is an extension of queue with following properties:
• Every item has a priority associated with it.
• An element with high priority is dequeued before an element with low priority.
• If two elements have the same priority, they are served according to their order in the queue.
A typical priority queue supports following operations:
• insert(item, priority): Inserts an item with given priority.
• getHighestPriority(): Returns the highest priority item.
• deleteHighestPriority(): Removes the highest priority item.
A priority queue can implemented using array-based sequences or linked lists.
10
References
Data Structures and Algorithms in Python. Michael H. Goldwasser, Michael T. Goodrich, and
Roberto Tamassia. Chapters 6, 7, 8, 10, 14
https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm
http://en.wikipedia.org/wiki/Priority_queue
https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm
http://en.wikipedia.org/wiki/Priority_queue