Skip to main content
Park JiHo Research notes Β· Seoul
KO

Data Structures for Coding Tests (1)

Linked lists, stacks and queues, with C++, Python and Swift examples.

ν•œκ΅­μ–΄ 원문

English edition note: The O(1) linked-list insertion/deletion bound assumes the relevant node or position is already available. For an array, O(1) describes indexed access, not a general value search. The active Python queue example uses deque. The code is retained as a historical example; its C++ size-format strings need type checking before reuse.

#πŸ“– Linked List

Linked lists contrast with arrays in these notes. Linked list: insertion and deletion O(1); search O(N). Array: insertion and deletion O(N); access O(1).

#πŸ“– stack : LIFO

  • Insertion and deletion O(1),
  • Search O(N)

#Using a stack in C++

//C++
#include <iostream>
#include <stack>
using namespace std;

stack<int> s;
s.push(7);
s.push(5);
s.push(4);
printf("size: %d\n", s.size());
while(!s.empty()){
  printf("%d\n", s.top()); //Print the top value
  s.pop(); //Remove the top value without printing it
}

#Using a stack in Python

#Python
s = []
s.append(7)
s.append(5)
s.append(4)
print("size: ", len(s))
while len(s) > 0:
  print(s[-1])
  s.pop()

Here, the index [-1] refers to the last element of the list.

#Using a stack in Swift

//Swift
var s = [Int]()
s.append(7)
s.append(5)
s.append(4)
print("size: ", s.count)
while !s.isEmpty {
  print(s.last!)
  s.removeLast()
}

#πŸ“– queue : FIFO

  • Insertion and deletion O(1),
  • Search O(N)

#Using a queue in C++

//C++
#include <iostream>
#include <queue>
using namespace std;

queue<int> q;
q.push(7);
q.push(5);
q.push(4);
printf("size: %d\n", q.size());
while(!q.empty()){
  printf("%d\n", q.front());
  q.pop();
}

#Using a queue in Python (list-based implementation)

#Python
"""
from queue import Queue
q = Queue()
q.put(7)
q.put(5)
q.put(4)
print("size: ", q.qsize())
while not q.empty():
  print(q.get()) #Print the front value

thread-safe : A data structure safe for multithreaded use (with synchronization overhead)
"""
#Use the deque library
from collections import deque

q = deque()
q.append(7)
q.append(5)
q.append(4)
print("size: ", len(q))
while len(q) > 0:
  print(q[0])
  q.popleft() #Remove from the front (queue)
  #q.pop() #Remove from the back (stack)
  • A deque is also available in C++.

Connect