DATA STRUCTURE

• empty() – Returns whether the stack is empty – Time Complexity: O(1)
• size() – Returns the size of the stack – Time Complexity: O(1)
• top() / peek() – Returns a reference to the topmost element of the stack – Time Complexity: O(1)
• push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)
• pop() – Deletes the topmost element of the stack – Time Complexity: O(1)

• Traverse: Go through the elements.
• Search: Search for an element by value or index.
• Update: Update the value of an existing element at a given index.
• Delete and Insert: 由于array是fixed- length, 无法直接实现这些操作，可以通过创建一个新的array with (size+1), 然后复制current array.

• Build blocks for other data structures such as array lists, heaps, hash tables, vectors, and matrices.
• Used for different sorting algorithms such as insertion sort, quick sort, bubble sort, and merge sort.

• Elements in a linked list are known as nodes.
• Each node contains a key and a pointer to its successor node, known as next.
• The attribute named head points to the first element of the linked list.
• The last element of the linked list is known as the tail.

• Singly linked list — Traversal of items can be done in the forward direction only.
• Doubly linked list — Traversal of items can be done in both forward and backward directions. Nodes consist of an additional pointer known as prev, pointing to the previous node.
• Circular linked lists — Linked lists where the prev pointer of the head points to the tail and the next pointer of the tail points to the head.

• Search: Find the first element with the key k in the given linked list by a simple linear search and returns a pointer to this element.
• Insert: Insert a key to the linked list. An insertion can be done in 3 different ways; insert at the beginning of the list, insert at the end of the list, and insert in the middle of the list.
• Delete: Removes an element x from a given linked list. You cannot delete a node in a single step. A deletion can be done in 3 different ways; delete from the beginning of the list, delete from the end of the list, and delete from the middle of the list.

• Introduce the existing module in Python - collections.deque
  • In Python, there’s a specific object in the collections module that you can use for linked lists called deque (pronounced “deck”), which stands for double-ended queue.
  • collections.deque uses an implementation of a linked list in which you can access, insert, or remove elements from the beginning or end of a list with constant O(1) performance.

    >>> deque(['a','b','c']) # input has to be an iterable object, if not then new deque would be empty.
    deque(['a', 'b', 'c'])
    
    >>> deque('abc')
    deque(['a', 'b', 'c'])
    
    >>> deque([{'data': 'a'}, {'data': 'b'}])
    deque([{'data': 'a'}, {'data': 'b'}])

  • For more info: https://docs.python.org/3/library/collections.html#collections.deque

• Implement your own Linked List - 待完善

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return self.data

class LinkedList:
    def __init__(self):
        self.head = None

    def __repr__(self):
        node = self.head
        nodes = []
        while node is not None:
            nodes.append(node.data)
            node = node.next
        nodes.append("None")
        return " -> ".join(nodes)

>>> llist = LinkedList()
>>> llist
None

>>> first_node = Node("a")
>>> llist.head = first_node
>>> llist
a -> None

>>> second_node = Node("b")
>>> third_node = Node("c")
>>> first_node.next = second_node
>>> second_node.next = third_node
>>> llist
a -> b -> c -> None

class HashTable:

	# Create empty bucket list of given size
	def __init__(self, size):
		self.size = size
		self.hash_table = self.create_buckets()

	def create_buckets(self):
		return [[] for _ in range(self.size)]

	# Insert values into hash map
	def set_val(self, key, val):
	
		# Get the index from the key
		# using hash function
		hashed_key = hash(key) % self.size
		
		# Get the bucket corresponding to index
		bucket = self.hash_table[hashed_key]

		found_key = False
		for index, record in enumerate(bucket):
			record_key, record_val = record
			
			# check if the bucket has same key as
			# the key to be inserted
			if record_key == key:
				found_key = True
				break

		# If the bucket has same key as the key to be inserted,
		# Update the key value
		# Otherwise append the new key-value pair to the bucket
		if found_key:
			bucket[index] = (key, val)
		else:
			bucket.append((key, val))

	# Return searched value with specific key
	def get_val(self, key):
	
		# Get the index from the key using
		# hash function
		hashed_key = hash(key) % self.size
		
		# Get the bucket corresponding to index
		bucket = self.hash_table[hashed_key]

		found_key = False
		for index, record in enumerate(bucket):
			record_key, record_val = record
			
			# check if the bucket has same key as
			# the key being searched
			if record_key == key:
				found_key = True
				break

		# If the bucket has same key as the key being searched,
		# Return the value found
		# Otherwise indicate there was no record found
		if found_key:
			return record_val
		else:
			return "No record found"

	# Remove a value with specific key
	def delete_val(self, key):
	
		# Get the index from the key using
		# hash function
		hashed_key = hash(key) % self.size
		
		# Get the bucket corresponding to index
		bucket = self.hash_table[hashed_key]

		found_key = False
		for index, record in enumerate(bucket):
			record_key, record_val = record
			
			# check if the bucket has same key as
			# the key to be deleted
			if record_key == key:
				found_key = True
				break
		if found_key:
			bucket.pop(index)
		return

	# To print the items of hash map
	def __str__(self):
		return "".join(str(item) for item in self.hash_table)


hash_table = HashTable(50)

# insert some values
hash_table.set_val('gfg@example.com', 'some value')
print(hash_table)
print()

hash_table.set_val('portal@example.com', 'some other value')
print(hash_table)
print()

# search/access a record with key
print(hash_table.get_val('portal@example.com'))
print()

# delete or remove a value
hash_table.delete_val('portal@example.com')
print(hash_table)