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

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

 

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

 

양방향 = 앞 뒤 모두 접근 가능한 것

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

class DoublyLinkedList:

	def __init__(self,item):
    	self.nodeCount = 0 

        #더미노드 앞뒤로 추가 
        self.head = Node(None)
        self.tail = Node(None)
        
        #head와 tail 연결 
        self.head.prev = None 
        self.head.next = self.tail 
        self.tail.prev = self.head
        self.tail.next = None

 

#리스트 순회 

def traverse(self):
	result = []
    curr = self.head
    
    while curr.next.next :    #현재의 다음 다음이 존재할 경우로 조건 수정 (tail더미 있어서 가능)
    	curr = curr.next
        result.append(curr.data)
    return result 
    
#리스트 역순회

def reverse(self):
	result = []
    curr = self.tail
    
    while curr.prev.prev:
    	curr = curr.prev
        result.append(curr.data)
    return result 
    
#원소 삽입 

def.insertAfter(prev,newNode)
	next = prev.next 
    #연결하기 
    newNode.prev = prev 
    newNode.next = next 
    #기존 링크 끊기
    prev.next = newNode
    next.prev = newNode
    
    self.nodeCount +=1
    return True 
    
#특정 원소 얻어내기 :head에만 더미 있을때랑 동일 

def getAt(self,pos):
	if pos <0 or pos > self.nodeCount : return None
    
    if pos > self.nodeCount//2 : #tail부터 세보자 
    	i = 0
    	curr = self.tail
    	while i< self.nodeCount-pos+1:
    		curr = curr.prev 
        	i+=1 
            
    else: #아니면 head부터 세보자 
    	i = 0
        curr = self.head
        while i < pos:
        	curr = curr.next
            i+=1 

    return curr 
    
#원소 삽입 

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

 

연습문제 

    def popAfter(self, prev):
        
        curr = prev.next
        next = curr.next 
        
        prev.next = next 
        next.prev = prev 
        
        self.nodeCount -=1 
        
        return curr.data 

    def popBefore(self, next):
        
        curr = next.prev 
        prev = curr.prev 
        
        prev.next = next
        next.prev = prev 
        
        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)
            
    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