CS计算机代考程序代写 python data structure c/c++ chain flex algorithm 1

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