프로그래머스 강좌, 자료구조와 알고리즘 - 3

자료구조와 알고리즘 - 3 link

14강. 큐(Queues)

큐는 Stack과 달리 선입선출(FIFO; First-In First-Out) 의 순서로 제어됩니다. 리스트 속에 데이터들의 시작과 끝의 포인터가 존재합니다. 입력(enqueue)시, 리스트의 rear pointer에 추가되며 출력(dequeue)시, 리스트의 front pointer 부분을 꺼내게 됩니다.

실습

목표: 배열과 양방향 연결 리스트 구현시, 연산 복잡도 확인

배열 - 출력시, 모든 개체의 위치를 옮기는 과정에서 O(n) 가 소요
양뱡향 연결 리스트 - 포인터만 변경하게 됨으로 O(1) 소요

15강. 환형 큐(Circular Queue)

dequeue 과정에서 발생한 front pointer 앞의 공간을 재사용하지 못하는 큐의 단점을 개선하여 리스트의 시작과 끝을 이음으로써 재사용 가능

실습

목표: 환형큐의 enqueue, dequeue, peek 구조를 구현

범위가 제한된 배열을 환형으로 이어서 쓴다는점을 감안하여 배열의 끝과 처음을 연속적으로 사용

16강. 우선순위 큐(Priority Queues)

FIFO 의 특성을 가진 일반적인 큐와 달리 우선순위에 따라 enqueue나 , dequeue의 대상이 선택되는 방식.

실습

목표: 양방향 리스트를 통해 enqueue할 때, 순차검색을 통해 일치하는 위치에 넣는 방식 사용, data의 값이 클수록 높은 우선순위.

enqueue => O(n), dequeue = O(1)
트리구조 사용시 더 유용하나 다음 과정에 진행, 퀵정렬과 비슷한 느낌일것으로 예상

17강. 트리(Trees)

트리의 각 노드를 정해진 순서로 방문하는 것, 순회 (traversal) 연산.

• 깊이 우선 순회 (DFT; Depth First Traversal)
• 넓이 우선 순회 (BFT; Breadth First Traversal)

DFT (Depth First Traversal) vs DFS (Depth First Search)? link

1. DFT는 DFS를 사용합니다.
2. DFS가 연결된 그래프에 적용되는 알고리즘 인 반면, DFT는 일반적으로 연결이 끊어진 그래프에 적용되는 순회입니다.
3. DFS는 DFT가 수행하는 동안 각각의 모든 노드를 방문 할 것이라고 보증하지 않았습니다.

하지만 같은것이라 보아도 크게 문제되지 않습니다. 두 용어 모두, 그래프 또는 트리 (모든 트리는 또한 그래프이기도 합니다) 를 대상으로 노드들을 방문하는 순서를 규정하는 방식을 뜻합니다.

근데 tree보단 root모양인데 왜 그렇게 굳어진걸까?

18강. 이진 트리(Binary Trees)

모든 노드의 자식노드; 차수가 2 이하인 트리구조

깊이 우선 순회(DFT; Depth First Traversal)

• 중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤 노드 x 를 방문, 그리고 나서 오른쪽 서브트리를 순회
• 전위 순회 (pre-order traversal): 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회
• 후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문

실습 1

목표: 이진트리의 depth 값 계산하는 기능 구현

class Node:
 # 초기화 & size()
 
    def depth(self):
        # 재귀적으로 호출하며 단말노드 부터 체크
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        # l 과 r 변수에 좌우 노드의 깊이값 저장
        return (l if l > r else r) + 1
        
class BinaryTree:
 # 초기화 & size()
 
    def depth(self):
        # 루트값 유무 확인
        if self.root:
            # root node 부터 depth 확인절차 진행
            return self.root.depth()
        else:
            return 0

실습 2, 3 - 깊이 우선 순회(DFT; Depth First Traversal)

목표: 이진트리의 전위순회, 후위순회 연산 기능 구현

class Node:
 # 초기화 & inorder()
 
 def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal
    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal

class BinaryTree:
 # 초기화 & inorder()
 
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []
    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

19강 이진 트리 - 넓이 우선 순회(BFT; Breadth First Traversal)

BFT는 트리 구조에서 낮은 level 중 왼쪽 노드부터 순회하게 됩니다. 이로써 DFT와 달리 재귀적으로 구현이 불가합니다. 하지만 Queue를 사용하여 다음에 방문할 노드를 enqueue 해두고 dequeue 하게되면 각각의 level별로 노드를 순회하게 됩니다.

실습

목표: 넓이 우선 순회 기능을 구현

    def bft(self):
        traversal = []
        queue = ArrayQueue()

  # root 존재여부 확인
        if self.root:
            queue.enqueue(self.root)

  # 하위 노드를 queue에 추가하며 노드의 값을 저장
        while not queue.isEmpty():
            node = queue.dequeue()
            traversal.append(node.data)
            if node.left:
                queue.enqueue(node.left)
            if node.right:
                queue.enqueue(node.right)

        return traversal

20강. 이진 탐색 트리(Bianry Search Trees) (1)

시간복잡도

1. Search Operation - O(n)
2. Insertion Operation - O(1)
3. Deletion Operation - O(n)

퀵정렬의 알고리즘을 트리의 형태로 접근하는 방식으로 생각하면 될 것 같다.

실습

목표: BST 에 insert 기능을 구현

    def insert(self, key, data):
     # 키 중복시 예외
        if self.key is key:
            raise KeyError('inserted key is duplicated')

        # key의 비중 확인
        if self.key > key:
            # 하위노드 존재여부 대응
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif self.key < key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
                
        return True

21강. 이진 탐색 트리(Binary Search Trees) (2)

트리노드 삭제시 고려사항 참조

1. 하위노드 X
   
2. 1개의 하위노드
   
3. 2개의 하위노드
   

3번을 처리하며 1, 2의 과정 모두 처리가능

def remove(self, key):
    node, parent = self.lookup(key)

    if node:
        nChildren = node.countChildren()
        
        if nChildren is 0: #하위노드 0개
            if parent:
                if node.key is parent.left.key:
                    parent.left = None
                else:
                    parent.right = None
            else:
                self.root = None
            
        elif nChildren is 1: #하위노드 1개
            childNode = None
            if node.left:
                childNode = node.left
            else:
                childNode = node.right
                
            if parent:
                if node.key is parent.left.key:
                    parent.left = childNode
                else:
                    parent.right = childNode
            else:
                self.root = childNode
                
        else: #하위노드 2개
            parent = node
            successor = node.right
            while successor.left:
                parent = successor
                successor = successor.left
                
            node.key = successor.key
            node.data = successor.data
            
            if successor.key is parent.left.key:
                parent.left = successor.right
            else:
                parent.right = successor.right

        return True

    else:
        return False

22강. 힙(Heaps)

힙 (heap) 도 이진 트리의 한 종류이며 이진 힙 (binary heap) 이라고도 불립니다.

힙에는 최대 힙 (max heap) 과 최소 힙 (min heap) 이 있습니다. 최대 힙과 최소 힙은 데이터 원소의 순서 기준이 내림차순이냐 오름차순이냐만 달라지고 완전히 대칭이므로, 여기에서는 최대 힙을 기준으로 설명을 전개하겠습니다. 최대 힙은 세 가지의 성질을 유지하고 있는 이진 트리입니다. 그 세 가지 성질은:

• 루트 노드가 항상 최댓값을 가진다.
• 완전 이진 트리이다. (최하위 레벨을 제외하고 모든 레벨이 차있는 상태)
• 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.

완전이진트리의 제약조건으로 인해 log(n)에 비례하는 실행시간을 가짐

배열을 이용해 이진트리 표현시 index 는
*노드 번호 n 기준

• 상위 : m // 2
• 좌측 하위: 2 * n
• 우측 하위: 2 * n + 1

실습

목표: 새로운 노드 추가

    def insert(self, item):
        self.data.append(item)
        index = len(self.data)-1
        
        while index > 1:
            if(self.data[index] > self.data[index // 2]):
             # 아래 방법으로도 손쉽게 값 교환을 할 수 있었다.
             # self.data[index], self.data[index // 2] = self.data[index // 2], self.data[index]
                self.data[index] = self.data[index // 2]
                self.data[index // 2] = item
                index = index // 2
            else:
                break

23강. 힙(Heaps) (2)

최대 힙에서의 삭제. logn의 복잡도

1. 루트노드의 제거 (루트노드에 최대값이 위치)
2. 트리의 마지막 노드를 루트노드로 이동
3. 양쪽 자식노드보다 작을때 까지 서로 값을 교환 (자식노드 중 둘다 클경우 더 큰쪽으로)

최대/최소 힙의 응용

우선 순위 큐 (priority queue)
삽입(enqueue)시, 느슨한 정렬(=반정렬; 큰값이 상위, 작은값이 하위에 있음)을 이루고 있도록 함. O(logn) 의 복잡도
출력(dequeue)시, 최대값을 순서대로 추출. O(logn) 의 복잡도

힙 정렬 (heap sort)
정렬되지 않은 원소를 최대힙에 삽입, O(logn) X 힙이 빌때까지 삭제순으로 정렬, O(logn) = O(nlogn)

Read more →

프로그래머스 강좌, 자료구조와 알고리즘 - 2

자료구조와 알고리즘 - 2 link

10강. 양뱡향 연결 리스트(Doubly Linked Lists)

노드간 참조공간을 뒤따라 오는 개체 참조 외에도 앞서오는 개체 참조공간도 생성하여
앞에서 뒤로, 뒤에서 앞으로 링크가 되어있는 형태

class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None
        
class DoublyLinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'
        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s

    def getLength(self):
        return self.nodeCount

    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result

    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None
        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1
        return curr

    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)

실습1

목표: 리스트를 역순으로 출력하는 함수 구성

 def reverse(self):
     target = self.tail
     returnList = []

     while target.prev is not self.head:
         returnList.append(target.prev.data)
         target = target.prev
     
      return returnList

실습2

목표: 선택된 next 앞에 newNode 삽입

    def insertBefore(self, next, newNode):
        if next is self.head:
            return False
            
        next.prev.next = newNode
        newNode.prev = next.prev
        newNode.next = next
        next.prev = newNode

        self.nodeCount += 1
        return True

실습3

목표: 값을 뽑아내는 popAfter(), popBefore(), popAt() 구현 / popAt()은 popAfter()나 popBefore()를 사용해 구현

    def popAfter(self, prev):
        if prev is self.tail:
            return None
        targetNode = prev.next

        prev.next = targetNode.next
        targetNode.next.prev = prev
        self.nodeCount -= 1
        return targetNode.data

    def popBefore(self, next):
        if next is self.head:
            return None
        targetNode = next.prev

        next.prev = targetNode.prev
        targetNode.prev.next = next
        self.nodeCount -= 1
        return targetNode.data

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        if self.nodeCount is 1 or pos is 1:
            return self.popAfter(self.head)
        else:
            prevNode = self.getAt(pos-1)
            return self.popAfter(prevNode)

실습4

목표: 전달받은 리스트를 뒤에 병합하는 기능 구현

    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail
        
        self.nodeCount += L.nodeCount

다른사람의 풀이를 통해 python은 , 를 통해 한번에 여러 대입이 가능함을 알았다. 상당히 직관적인 프로그래밍이 가능한 것 같다. 하지만 가독성으로는 기존 방식이 더 유리한듯 하다.

11강. 스택(Stacks)

후입선출(LIFO; Last In - First Out)로써 데이터의 입출이 동작하는 형태의 자료구조

• size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함
• isEmpty(): 현재 스택이 비어 있는지를 판단 (size() == 0?)
• push(x): 데이터 원소 x 를 스택에 추가
• pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거 (또한, 반환)
• peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class ArrayStack:
 def __init__(self):
  self.data = []
 def size(self):
  return len(self.data)
 def isEmpty(self):
  return self.size() == 0
 def push(self, item):
  self.data.append(item)
 def pop(self):
  return self.data.pop()
 def peek(self):
  return self.data[-1]

class LinkedListStack:
 def __init__(self):
  self.data = DoublyLinkedList()
 def size(self):
  return self.data.getLength()
 def isEmpty(self):
  return self.size() == 0
 def push(self, item):
  node = Node(item)
  self.data.insertAt(self.size() + 1, node)
 def pop(self):
  return self.data.popAt(self.size())
 def peek(self):
  return self.data.getAt(self.size()).data

실습

목표: stack 을 이용한 완성된 괄호( ) 와 같은 형태가 존재 여부를 확인하는 기능

class ArrayStack:
    def __init__(self):
        self.data = []
    def size(self):
        return len(self.data)
    def isEmpty(self):
        return self.size() == 0
    def push(self, item):
        self.data.append(item)
    def pop(self):
        return self.data.pop()
    def peek(self):
        return self.data[-1]

def solution(expr):
    match = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    S = ArrayStack()
    for c in expr:
        if c in '({[':
         S.push(c)
        elif c in match:
            if S.isEmpty():
                return False
            else:
             t = match[c]
                if t != S.pop():
                    return False
    return S.isEmpty()

12강. 스택의 응용 - 수식의 후위 표기법 (Postfix Notation)

중위표기법 (A+(B*C))-(D/E) - 연산자를 피연산자 사이에 표시, 일반적인 표기법
전위표기법 -+A*BC/DE - 연산자를 먼저, 피연산자를 나중에 표시
후위표기법 ABC*+DE/- - 피연산자를 먼저, 연산자를 나중에 표시

실습

목표: 괄호 유무에 상관없이 중위 표기를 후위 표기로 변경하는 기능 구현

에러 수정필요

def solution(S):
    opStack = ArrayStack()
    answer = ''
    
    for c in S:
        if c in prec:
            if c is not '(' and not opStack.isEmpty() and prec[opStack.peek()] >= prec[c]:
                answer += opStack.pop()
            opStack.push(c)
        elif c is ')':
            while True:
                op = opStack.pop()
                if op is not '(':
                 break
                answer += op
        else:
            answer += c
            
    while not opStack.isEmpty():
        op = opStack.pop()
        if op is not '(':
            answer += op
        
    return answer

A-(B-C)-D*(E/F)+G 처리 요청시, ABC--DEF/*-G+ 가 아닌 ABC--DEF/*G+-로 처리된다. 이유는?

python에선 값을 while 문안에서 할당하여 바로 비교하는 연산은 불가하다고 한다. 참조

13강. 후위 표기 수식 계산

실습

목표: 후위 표기법으로 전달받은 수식을 연산하여 반환

# infixToPostfix 메소드는 12강의 solution 사용

def postfixEval(tokenList):
    evalStack = ArrayStack()
    
    for t in tokenList:
        if isinstance(t,int):
            evalStack.push(t)
        else: #isOperator
            y = evalStack.pop()
            x = evalStack.pop()
            if t is '+':
                evalStack.push(x + y)
            elif t is '-':
                evalStack.push(x - y)
            elif t is '*':
                evalStack.push(x * y)
            else:
                evalStack.push(x / y)
    
    return evalStack.peek()

Read more →

프로그래머스 강좌, 자료구조와 알고리즘 - 1

자료구조와 알고리즘 - 1 link

1강은 소개로 생략

2강. 선형 배열(Linear Array)

python 의 list는 자료형의 제한이 없음
O(1) 작업

• 원소 덧붙이기 .append()
• 원소 하나를 꺼내기 .pop()

O(n) 작업

• 원소 삽입하기 .insert()
• 원소 삭제하기 .del()

기타

• 원소 탐색하기: .index()

실습1

목표: 리스트 L 에서 오름차순에 맞게 x의 값을 삽입

def solution(L, x):
    for i, v in enumerate(L):
        if v > x:
            L.insert(i, x)
            break
    else:
        L.append(x)
    return L

실습2

목표: 리스트 L 에서 x 값의 index 반환, 부재시 -1 반환

def solution(L, x):
    answer = []
    for i, v in enumerate(L):
        if v == x:
            answer.append(i)
    if len(answer) == 0:
        answer.append(-1)
    
    return answer

3강. 정렬과 탐색(Sorting & Searching)

내장 정렬기능

1. 파이썬 내장 함수 sorted() - 정렬된 리스트 반환(deep copy)
2. 리스트에 쓸 수 있는 메서드 .sort() - 해당 리스트 정렬

역순 정렬(reverse)
reverse=true 를 매개변수로 전달
ex) sorted(L, reverse=true), L.sort(reverse=true)

정렬방식 지정(key)
java의 Comparator 와 유사. sorted(L, key=lambda x: len(x)) 로 사용시 L 리스트의 개체값의 문자열 길이가 짧은 순으로 정렬 진행. dictionary 자료형도 L.sort(key=lambda x:x['score'], reverse=true) 의 형태로 x[‘score’] 값이 큰순으로 정렬가능.

탐색 알고리즘

1. 선형 탐색(linear search) - 순차적으로 탐색과정 진행, O(n)
2. 이진 탐색(binary search) - 정렬되어있는 경우 가능, 절반씩 쪼개며 탐색, O(logn)

실습1

목표 : 효율성을 위해 이진탐색으로 오름차순 정렬된 배열에서 x의 index값을 반환, 부재시 -1 반환

def solution(L, x):
    low=0
    high=len(L)-1
    answer = 0
    while(low<=high):
        mid=(low+high)//2
        if L[mid]==x:
            answer = mid
            break
        elif L[mid]>x:
            high=mid-1
        else:
            low=mid+1
    else:
     return -1
    return answer

4강. 재귀 알고리즘(Recursive Algorithms) 기초

실습1

목표 : 피보나치 수열 구현

• 재귀

  def solution(x):
      answer = 0;
      if x <= 1:
          answer = x
      else:
          answer = solution(x-1) + solution(x-2)
      return answer
  

• 반복문

  def solution(x):
      answer = 0;
      if x <= 1:
          answer = x
      else:
          now = 1;
          before = 0;
          for i in range(1, x):
              answer = before + now
              before = now
              now = answer
      return answer
  

5강. 재귀 알고리즘(Recursive Algorithms) 응용

자원 효율: 재귀적 < 반복적

실습1

목표: 재귀적 이진탐색 구현

def solution(L, x, l, u):
    if x < L[l] or x > L[u]:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l , mid - 1)

    else:
        return solution(L, x, mid + 1 , u)

6강. 알고리즘의 복잡도 (Comlexity of Algorithms)

점근적 표기법

• Big-θ : 평균적인 복잡도, θ(n) 로 표기
• Big-O : 최악의 경우 복잡도 (주로 사용), O(n) 로 표기
• Big-Ω : 최선의 경우 복잡도, Ω(n) 로 표기

정렬 알고리즘 예시 - 병합 정렬( merge sort)
정렬할 배열들을 각각 최소 비교단위로 분리하여 비교 -> O(logn)
정렬된 최소 비교단위 배열을 병합 - > O(n) => O(nlogn)

6강 실습. X

7강. 연결 리스트(Linked Lists) (1)

단방향 연결 리스트

다음 대상에 대한 주소를 참조하여 리스트를 구조화

• 특정 원소 참조 (k 번째)
• 리스트 순회 (list traversal)
• 길이 얻어내기

실습1

목표: linked list를 순회하며 각 노드값을 리스트로 만들어 반환하는 traverse 함수구현

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

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

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    def traverse(self):
        returnList = []
        target = self.head
        while target is not None:
            returnList.append(target.data)
            target = target.next
        
        return returnList

8강. 연결 리스트(Linked List) (2)

• 원소의 삽입 (insertion)
• 원소의 삭제 (deletion)
• 두 리스트 합치기 (concatenation)

9강.연결 리스트(Linked List) (3)

dummy node 를 linked list 의 head로 추가

class Node:
 def __init__(self, item):
  self.data = item
  self.next = None
  
class LinkedList:
 def __init__(self):
  self.nodeCount = 0
  self.head = Node(None)
  self.tail = None
  self.head.next = self.tail

 def __repr__(self):
  if self.nodeCount == 0:
   return 'LinkedList: empty'
   
  s = ''
  curr = self.head
  while curr.next:
   curr = curr.next
   s += repr(curr.data)
   if curr.next is not None:
    s += ' -> '
  return s

 def getLength(self):
  return self.nodeCount

 def traverse(self):
  result = []
  curr = self.head
  while curr.next:
   curr = curr.next
   result.append(curr.data)
  return result

 def getAt(self, pos):
  if pos < 0 or pos > self.nodeCount:
   return None
  i = 0
  curr = self.head
  while i < pos:
   curr = curr.next
   i += 1

  return curr

 def insertAfter(self, prev, newNode):
  newNode.next = prev.next
  if prev.next is None:
   self.tail = newNode
  prev.next = newNode
  self.nodeCount += 1
  return True

 def insertAt(self, pos, newNode):
  if pos < 1 or pos > self.nodeCount + 1:
   return False
  if pos != 1 and pos == self.nodeCount + 1:
   prev = self.tail
  else:
   prev = self.getAt(pos - 1)
  return self.insertAfter(prev, newNode)

 def concat(self, L):
  self.tail.next = L.head.next
  if L.tail:
   self.tail = L.tail
  self.nodeCount += L.nodeCount

실습1

목표: 노드를 뽑아내는 함수 구현

def popAfter(self, prev):
    curr = prev.next
    if prev.data is None:
        prev.next = curr.next
        self.tail = curr.next
    elif prev.next == self.tail:
        prev.next = None
        self.tail = prev
    else:
        prev.next = curr.next

    self.nodeCount -= 1
    return curr.data


def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        raise IndexError

    prev = self.getAt(pos - 1)
    return self.popAfter(prev)

Read more →