[Python] Data structures - Stack, Queue

Basic data structures

• array, list, tuple
• linked list
• set, dictionary
• graph, tree
• stack, queue

Stack(=array)

• 선입후출
• 리스트 라이브러리 이용
• append(): 리스트의 가장 뒤쪽에 데이터 삽입
• pop(): 리스트의 가장 뒤쪽에서 데이터 꺼냄

Queue

• 선입선출
• collections 모듈에서 제공하는 deque 자료구조 활용
• 속도가 리스트 자료형에 비해 효율적이며, queue 라이브러리를 이용하는 것보다 더 간단 
• from collections import deque queue = deque() queue.append((x,y)) x, y = queue.popleft()​

Linked List

Why?(=Array limitation)

• The size array is fixed
• Insertion of a new element / Deletion of a existing element in an array is expensive

Drawbacks of Linked List

hard to access specific element, need to access elements sequentially starting from the first element

 

Representation of the linked list

# Node class
class Node:
 
    # Function to initialize the node object
    def __init__(self, data):
        self.data = data  # Assign data
        self.next = None  # Initialize next as null
 
# Linked List class
class LinkedList:
   
    # Function to initialize the Linked List object
    def __init__(self):
        self.head = None

Insertion

class LinkedList:
   
    # Function to initialize the Linked List object
    def __init__(self):
        self.head = None
        
    # Function to insert a new node at the beginning
    def push(self, new_data):

        # 1 & 2: Allocate the Node &
        #        Put in the data
        new_node = Node(new_data)

        # 3. Make next of new Node as head
        new_node.next = self.head

        # 4. Move the head to point to new Node
        self.head = new_node

	# Function to insert a new node after the given prev_node
     def insertAfter(self, prev_node, new_data):

        # 1. check if the given prev_node exists
        if prev_node is None:
            print("The given previous node must inLinkedList.")
            return

        # 2. Create new node & 3. Put in the data
        new_node = Node(new_data)

        # 4. Make next of new Node as next of prev_node
        new_node.next = prev_node.next

        # 5. make next of prev_node as new_node
        prev_node.next = new_node
  
  
    # Appends a new node at the end.
    def append(self, new_data):

            # 1. Create a new node
            # 2. Put in the data
            # 3. Set next as None
            new_node = Node(new_data)

            # 4. If the Linked List is empty, then make new node as head
            if self.head is None:
                self.head = new_node
                return

            # 5. Else traverse till the last node
            last = self.head
            while (last.next):
                last = last.next

            # 6. Change the next of last node
            last.next = new_node

참고

[책] 이것이 취업을 위한 코딩테스트이다

https://www.geeksforgeeks.org/insertion-in-linked-list/