[자료구조와 알고리즘] #3. 연결리스트:단방향

프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?'를 학습하며 정리한 내용입니다. 

어서와! 자료구조와 알고리즘은 처음이지?

 

연결된 리스트 

구성 요소

• 노드 : 데이터 + 링크 
  • 데이터
    • e.g. 67이라는 값이 데이터, 해당 데이터의 연결고리가 링크 
    • 노드 내의 데이터는 다른 구조로 이루어질 수 있음( 문자열, 레코드, 또 다른 연결리스트 등) 

#자료구조 정의 

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

 

특정 원소 참조 (k번째 참조)

참고 : 첫 노드를 0이 아닌 1로 지정한다 (구현 편의성)

def getAt(self,pos):                            #class LinkedList의 method 
	if pos <= 0 or pos > self.nodeCount:
    	return None 
        
    i = 1 
    curr = self.head.                          #우선 curr을 첫 노드로 설정 
    while i < pos :                            #i가 pos와 같아질때까지 curr을 하나씩 옮기기 
    	curr = curr.next 
        i +=1 
    return curr

리스트 순회

 def traverse(self):
        
     nodes = []                       #빈 리스트를 만든다 
     node = self.head                 #첫번째 노드값을 정의해준다 
         
     while node != None:              #노드가 비어있거나, 끝나지 않을때 까지 
         nodes.append(node.data)      #빈 리스트에 node.data를 담아준다 
         node = node.next             #노드를 다음 노드로 보내준다 
     return nodes

길이 얻어내기 

def getLength(self):
	return self.nodeCount

 

원소 삽입 

• 복잡도 
  • 맨 앞에 삽입할 경우 or 맨 뒤에 삽입할 경우 : O(1)
  • 중간에 삽입할 경우 : O(n) 

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:                              #삽입 위치가 맨 앞 
            newNode.next = self.head              #뉴노드의 다음 링크를 self.head로 선언
            self.head = newNode                   #기존 self.head를 뉴노드로 선언 

        else:
            if pos == self.nodeCount + 1:         #삽입 위치가 맨 뒤일 경우 
                prev = self.tail                  #prev를 기존 연결된리스트의 맨 끝으로 세팅 
            else:
                prev = self.getAt(pos - 1)        #중간일 경우, pos 전 노드를 previous로 설정 

            newNode.next = prev.next               #새로운 노드의 링크를 기존 prev의 다음 링크(pos+1)로 세팅 
            prev.next = newNode                    #기존 prev노드의 링크를 새로운 노드에 연결 

        if pos == self.nodeCount + 1:            #삽입위치 맨뒤에 대해서 후처리. tail에 nextlink를 newNode로 newNode의 next는 None으로
            self.tail = newNode

        self.nodeCount += 1                      #삽입되었으니 노드카운트 일 증가 
        return True

 

원소 삭제 

r = L.popAt(pos)

1. 삭제하고자 하는 원소 : curr(pos위치), 앞에 있는 원소 : prev(pos-1), 뒤에 있는 원소 : (pos+1)
2. pos-1 = prev으로 설정 
3. prev.next <- curr.next로 지정 (pos-1과 pos+1 연결)
4. curr의 데이터를 return 
5. nodeCount -=1  

예외 케이스

1. 삭제하려는 노드가 맨 앞일 때 
   1. prev가 없으므로, Head를 pos+1로 조정 
2. 리스트의 맨 끝 노드를 삭제할때
   1. Tail을 pos-1로 조정 
   2. 앞에서부터 찾아와야함 
3. 유일한(마지막까지 남아있던 노드) 노드는 어떻게 삭제해야 하는지 유의해야 함 

def popAt(self, pos):
        
     if pos<1 or pos>self.nodeCount:
         raise IndexError 
     
     else:
         curr = self.getAt(pos)
        
     #맨앞 
         if pos == 1:
             self.head = curr.next
             self.nodeCount -=1
             #마지막 남은 애였을 때 
             if self.nodeCount==0:
                 self.tail = curr.next #이건 왜 이렇게 되는건지 좀 더 생각해봐야 함 
             return curr.data 
         
         else :
             prev = self.getAt(pos-1)    
             prev.next = curr.next
             #맨뒤 
             if pos == self.nodeCount:
                 self.tail = prev
                
             self.nodeCount -=1
             return curr.data

두 리스트의 연결 

def concat(self, L):
    self.tail.next = L.head            #앞에있는 원래 리스트의 맨 끝을 이어붙이려는 L의 처음으로 연결 
    if L.tail:                         #만약 뒤의 L이 비어있을 경우를 방지하여, L.tail이 존재하는 경우에만  
        self.tail = L.tail             #self(두개이어붙여진상황)tail을 L.tail로 옮긴다
    self.nodeCount += L.nodeCount

 

Dummy node가 있는 경우 

• 문제점: insertAt, popAt의 경우 하나하나 pos를 따라가야함 → 특정 노드를 주고 이거 뒤에 바로 insert,pop하게 하자! 
• 해결책 : insertAfter(prev, newNode), popAfter(prev)
  • 맨 앞은 어떻게 해야하지? (prev가 없으므로..) 
  • 해결책 : 맨 앞에 dummy node를 추가해서 해보자 (dummy node = 0번) 

class LinkedList:

	def __init__(self):
		self.nodeCount = 0
		self.head = Node(None) #더미노드 정의 
		self.tail = None
		self.head.next = self.tail

 

이에 따라 연산정의가 조금씩 달라짐 

 

def traverse(self):
	result = []
	curr = self.head               #처음 시작할 때 curr = 헤드로 해주기 
	while curr.next: 
		curr = curr.next           #처음 시작할때 데이터는 None이므로 먼저 이동해주고 담기 
 		result.append(curr.data)
	return result
    
    
def getAt(self, pos):
	if pos < 0 or pos > self.nodeCount:       #첫 헤드가 none(0)이므로 0은 포함  
		return None

	i = 0                         #첫 헤드가 none(0)이므로 0부터 시작 
	curr = self.head
	while i < pos:
		curr = curr.next
		i += 1

	return curr
    
def insertAfter(self,prev,newNode):

	newNode.next = prev.next
    
    if pre.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 :                                   #맨 앞이어도 얘가 커버해줌(0이 더미라서)
    	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

 

연습문제 : popAfter , popAt

 

    def popAfter(self, prev):
        #prev뒤에 지울 값이 없을 경우 
        if prev.next == None : 
            return None
        else: 
            curr = prev.next         #현재는 이전의 다음 값 
            #맨 뒤의 값이었을 경우 
            if curr.next == None :
                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 
        else :
            prev = self.getAt(pos-1)
            
            return self.popAfter(prev)