Data Structure in Python (Updating)

Preface

Linear Data Structure

  1. Array: fix number, same type
  2. Linked list: single link
  3. Advanced linked list: double link
  4. Stack: last-in, first-out
  5. Queue: first-in, first-out
  6. Deque: double end queue, combination of stack and queue
  7. Matrix: using Numpy module

Non-linear Data Structure

  1. Binary Tree
  2. Heap
  3. Hash table
  4. Graph

Python Spec.

  1. List: most versatile, basic ops:

    • length
    • concatenation
    • repetition
    • membership
    • iteration
  2. Tuple: immutable, include a single comma if one element

  3. Dict:

    • no dup-key
    • key must be hashable
  4. Sets

    • No index
    • No duplicates
    • immutable
    • operations: union |, intersect &, difference -, subset <=, superset >=
  5. ChainMap

    • collection of dicts
    • order matters as a stack
    • updated as dict updates

Current section is a note of tutorials point

Linked List

A linked list is a node-within-node hierarchical structure, and it is not a built-in data structure in python.

Node

Node is a unit within a linked list, and it consists of two parts - value, and the next node, as shown below.

1
2
3
4
5
6
class Node:
"""each node
"""
def __init__(self, val=None):
self.val = val
self.next = None

Methods

Typically, there are three methods in a linked list.

Traverse

We can traverse all nodes in a linked list:

1
2
3
4
5
6
7
8
9
10
11
class linkedList:
"""Hierarch structure of linked list
"""
def __init__(self):
self.head = None

def traverse(self):
current = self.head
while current != None:
print(current.val)
current = current.next

Add

Adding a node to the head a special case, it’s pointing new_node.next to the object self.head represents, then let self.head represent the new_node object.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class linkedList:
"""Hierarch structure of linked list
"""
def __init__(self):
self.head = None

def add_head(self, val):
"""point new_node.next to self.head

Arguments:
val {'str'} -- content of the new node
"""
new_node = Node(val)

new_node.next = self.head
self.head = new_node

Besides, we can insert a node in a position denoted by index, traversal to the position by get “.next” method iteratively.

Mind that the head node is a special case, and position_node is more like a pointer, that’s why modifying position_node will change self.head.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class linkedList:
"""Hierarch structure of linked list
"""
def __init__(self):
self.head = None

def add_index(self, position, val):
"""add node at position-th node

Arguments:
position {int} -- index of position
val {str} -- content of the new node
"""
new_node = Node(val)
position_node = self.head

if position < 0:
return 'wtf'

elif position == 0: # be the head
self.add_head(val)

else:
for i in range(position-1): # point to the node before position
if position_node.next != None:
position_node = position_node.next
position -= 1
else:
return 'Position not existed!'

new_node.next = position_node.next
position_node.next = new_node

We can also insert a node by key, and mind the pointer problem again!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class linkedList:
"""Hierarch structure of linked list
"""
def __init__(self):
self.head = None

def add_key(self, key, val):
"""add node at node with key

Arguments:
key {str} -- key of node
val {str} -- content of the new node
"""
new_node = Node(val)
current_node = self.head

if current_node == None: # empty list
return 'No such key!'

if self.head.val == key: # found at head
self.add_head(val)
return

while current_node.next != None: # afterwards
if current_node.next.val == key:
new_node.next = current_node.next
current_node.next = new_node
return
current_node = current_node.next

return 'No such key!' # not found

And if we want to append a node without knowing either keys or indices, just exhaust all nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class linkedList:
"""Hierarch structure of linked list
"""
def __init__(self):
self.head = None

def append(self, val):
"""point last node.next to new_node

Arguments:
val {'str'} -- content of the new node
"""
new_node = Node(val)

if self.head == None: # consider empty
self.head = new_node
return

current = self.head.next # not empty
while current.next != None: # move pointer
current = current.next
current.next = new_node

Delete

Another useful method is deletion. In this case, we do it key-wise, and delete ALL node that have the given key value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class linkedList:
"""Hierarch structure of linked list
"""
def __init__(self):
self.head = None

def del_key(self, key):
"""delete node with designated key

Arguments:
key {'str'} -- val of node intend to be deleted
"""
current_node = self.head
count = 0

if self.head.val == key:
self.head = self.head.next
count +=1

while current_node.next != None:
if current_node.next.val == key:
current_node.next = current_node.next.next
count +=1
current_node = current_node.next

if count == 0:
return 'No such key!'
else:
return '%s deleted %d times.' % (key, count)
 上一篇

System Center Operations Manager SCOM