연결 리스트 (Linked Lists)

본격적으로 낯설기 시작한다.. 이러나 저러나 핵심은 'link'

장점 : 쉽다. (빠르다.)
단점 : 메모리 소요 크다. i번째 v 찾는데 선형 배열보다 느리다.(빠르다며? ∵i가 없어서 처음부터 link 타고 탐색해야 한다.)

1. 일단, 구현

class Node:
	def __init__(self, item):
          self.data = item
          self.next = None
# a = Node(3)이면, self.data가 3인 Node가 생성(초기화)됨.


class LinkedList:
	def __init__(self):
          self.nodeCount == 0
          self.head == None
          self.tail == None
# L = LinkedList() 이면, 빈 연결 리스트가 생성(초기화)됨.

	def getAt(self, pos):
    		if pos<1 or pos>self.nodeCount:
            		return None
                    # LinkedList는 1 <= pos <= nodeCount니까, 이외 값은 안 받아.
           	i = 1
            	curr = self.head
            # head부터 탐색 시작
            	while i < pos:
            		curr = curr.next
                    	i += 1
                    # link 타고 다음 탐색, i로 pos를 계산(count).
                    return curr
                    
        def traverse(self):
        	result = []
            	curr = self.head
            # 마찬가지로 head부터 탐색 시작
                while curr:
                    answer.append(curr.data)
                    curr = curr.next
                # curr이 참이면 data를 result에 추가하고 link 타고 다음 탐색
                return result
                
        def insertAt(self, pos, newNode):
        	if pos<1 or pos>self.nodeCount+1:
            		return False
                    # 연결 리스트 끝에 추가하는 경우 nodeCount+1.
            	if pos == 1:
                	newNode.next = self.head
                    	self.head = newNode
                    # 연결 리스트 처음에 추가하는 경우 newNode의 link를 기존 head로 하고, head를 newNode로 변경.
                else:
                	if pos == self.nodeCount+1:
                    		prev = self.tail
                        # 연결 리스트 끝에 추가하는 경우 기존 tail을 prev에 두고.
                    	else:
                        	prev = self.getAt(pos-1)
                        # 끝에 추가하는 경우가 아닌 경우 getAt(pos-1)을 prev에 둔다. (∵prev의 link를 newNode로 변경해야함.)
                        newNode.next = prev.next
                        prev.next = newNode
                        
                        if pos == self.nodeCount+1:
                        	self.tail = newNode
                            # 끝에 추가하는 경우 tail을 newNode로 변경.
                        self.nodeCount += 1
                    # nodeCount 1 증가 (∵ 1개의 newNode 추가)
                        return True
                        
         def popAt(self, pos):
         	if pos<1 or pos>self.nodeCount:
            		raise IndexError
            	curr = self.getAt(pos)
                if pos == 1:
                	self.head = self.head.next
                else:
                	prev = self.getAt(pos-1)
                    	prev.next = curr.next
                    	if pos == self.nodeCount:
                        	self.tail = prev
                self.nodeCount -= 1
                if self.nodeCount == 0:
                	self.head = None
                    self.tail = None
                return curr.data
            

2. 왜 이렇게 복잡해졌냐? 연결 리스트 처음에 newNode를 넣거나 뺄때 문제가 되니까..
그래서 data가 None인 이른바 dummy node를 head에 넣고 구현!

class LinkedList:
	def __init__(self):
          self.nodeCount = 0
          self.head = Node(None)
          self.tail = None
          self.head.next = self.tail
    	# 이렇게 해서 head에 dummy node 삽입하고 그 link를 tail로 초기화. 단, dummy node는 node로 count 하지 않는다.
        
    	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.codeCount:
            		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)
        # 삽입 코드가 쉬워짐. (∵ pos가 1이어도 신경 노노)
        
        def popAfter(self, prev):
            curr = prev.next
            if curr.data == None:
            	return None
            elif curr.next == None:
            	self.tail = prev
            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)
        # 삭제 코드 쉬워짐. (이상한 에러 걱정 노노)

한줄평

중요한 메인 (여기서는 연결리스트가 link로 작동한다는 점)에 집중할 수 있도록, 특별한 케이스들의 피할 수 있는 코드 필요해 보인다. (연결리스트 처음에 node를 넣거나 뺄 때 이슈를 회피).