방앗간

※ 연결 리스트 (Linked Lists) - 삽입과 삭제가 유연하다는 것이 가장 큰 장점이라고 볼 수 있다. - 맨 앞에 추가된, 데이터 원소를 담고 있지않은 노드를 더미 노드(dummy node)라고 부른다. #메서드 insertAt() 구현 def insertAt(self, pos, newNode): if 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)

※ 연결 리스트 (Linked Lists) (1). 삽입하려는 위치가 리스트 맨 앞일 때 > prev 없음, Head 조정 필요 (2). 삽입하려는 위치가 리스트 맨 끝일 때 > Tail 조정 필요 연결 리스트 원소 삽입의 복잡도 -맨 앞에 삽입하는 경우 : O(1) -중간에 삽입하는 경우: O(n) -맨 끝에 삽입하는 경우: O(1)

※ 연결 리스트 (Linked Lists) - 추상적 자료구조 (Abstract Data Structures) # 특정 원소 참조 def getAt(self, pos): if pos self.nodeCount: return None i = 1 curr = self.head while i < pos: curr = curr.next i += 1 return curr 배열 연결 리스트 저장 공간 연속한 위치 임의의 위치 특정 원소 지칭 매우 간편 선형탐색과 유사 O(1) O(n)