ALGORITHMS AND COMPLEXITY
farhankhan
Week3-Part1.pptxLinked Lists
Cat Kutay
Click on Insert > new slide to choose your cover, then delete this page.
Sequences
8/7/20 12:11 PM
1
Data Types
Simple versus structured
Concrete versus Abstract
Most important concrete data types
Arrays
Records
Linked Lists
Binary Trees
Graphs
Abstract Data Types
Integers
List
Queue
Stack
Click on Insert > new slide to choose your cover, then delete this page.
Collections in Python
List – ordered and changeable
Tuple – ordered and unchangeable
Set – unordered and unindexed (unless defined as a function of ‘i’)
Dictionary – unordered, changeable and indexed
Click on Insert > new slide to choose your cover, then delete this page.
Singly Linked List
A singly linked list is a concrete data structure consisting of a sequence of nodes, starting from a head pointer
Each node stores
element
link to the next node
next
elem
node
A
B
C
D
head
Click on Insert > new slide to choose your cover, then delete this page.
The Node Class for List Nodes
public class Node {
// Instance variables:
private Object element;
private Node next;
/** Creates a node with null references to its element and next node. */
public Node() {
this(null, null);
}
/** Creates a node with the given element and next node. */
public Node(Object e, Node n) {
element = e;
next = n;
}
// Accessor methods:
public Object getElement() {
return element;
}
public Node getNext() {
return next;
}
// Modifier methods:
public void setElement(
Object newElem) {
element = newElem;
}
public void setNext(
Node newNext) {
next = newNext;
}
}
Click on Insert > new slide to choose your cover, then delete this page.
Inserting at the Head
Allocate a new node (memory)
Insert new element
Make new node point to old head
Update head to point to new node
Click on Insert > new slide to choose your cover, then delete this page.
Removing at the Head
Update head to point to next node in the list
Allow garbage collector to reclaim the former first node
Click on Insert > new slide to choose your cover, then delete this page.
Inserting at the Tail
Find the tail node
Allocate a new node
Insert new element
Have new node point to null
Have old last node point to new node
Update tail to point to new node
Click on Insert > new slide to choose your cover, then delete this page.
Removing at the Tail
Removing at the tail of a singly linked list is not efficient!
There is no constant-time way to update the tail to point to the previous node
Click on Insert > new slide to choose your cover, then delete this page.
Spatial efficiency
Storage space is the space for storing the input: data and algorithm
Auxiliary Space is the extra space or temporary space used by an algorithm.
Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.
To compare standard sorting algorithms on the basis of space, then Auxiliary Space would be a better criteria than Space Complexity. Merge Sort uses O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though.
Click on Insert > new slide to choose your cover, then delete this page.
What is a stack
Stack is an Abstract Data Type
Stack defined as LIFO – last in first out
Has operations:
push, which adds an element to the collection, and
pop, which removes the most recently added element that is not yet removed.
Click on Insert > new slide to choose your cover, then delete this page.
Stack as a Linked List
We can implement a stack with a singly linked list
The top element is stored at the first node of the list
The space used is O(n) and each operation of the Stack ADT takes O(1) time
t
nodes
elements
Click on Insert > new slide to choose your cover, then delete this page.
Linked-List Stack in Python
13
Click on Insert > new slide to choose your cover, then delete this page.
What is a queue?
Abstract data type holds a collection of elements where they are added to the back of the queue and removed from the front of the queue.
The principle by which a queue is ordered is called FIFO (first-in first-out)
Click on Insert > new slide to choose your cover, then delete this page.
Queue as a Linked List
We can implement a queue with a singly linked list
The front element is stored at the first node
The rear element is stored at the last node
The space used is O(n) and each operation of the Queue ADT takes O(1) time
f
r
nodes
elements
Click on Insert > new slide to choose your cover, then delete this page.
Linked-List Queue in Python
Click on Insert > new slide to choose your cover, then delete this page.
Linked list and arrays
Array contains a collection of similar type data elements
Elements accessed by index
However insertion and deletion are slow
Memory is allocated at program compile
Click on Insert > new slide to choose your cover, then delete this page.
Search an element def search(Node head, int x)
Iterative
Initialize a node pointer, current = head.
While current is not NULL (ie next to tail)
If current.data is equal to the key being searched return true.
Else assign current = current.next
Return false
Click on Insert > new slide to choose your cover, then delete this page.
Recursive
If head is NULL, return false. //empty list
If head.data is same as x, return true;
Else return search(head.next, x)
Search an element def search(Node head, int x)
Click on Insert > new slide to choose your cover, then delete this page.
Swap elements
Swap (n1, n2)
If head=null list empty
If (n1 = n2 )return
Search for n1 , node1 = n1
Search for n2 , node2 = n2
Reassign node.nextnode for n1.previous and n2.previous
Reassign node.nextnode for n1 and n2
Click on Insert > new slide to choose your cover, then delete this page.
Double and Circular linked lists
Click on Insert > new slide to choose your cover, then delete this page.
Length of size
Set count = 0
Traverse list from head to tail and increment count
Return count
Click on Insert > new slide to choose your cover, then delete this page.
What is a tree
Click on Insert > new slide to choose your cover, then delete this page.
