양방향 연결 리스트(Doubly Linked Lists)

앞 으로도 뒤로도 진행 가능

기본형 양방향 연결 리스트

def__init__(self,item):
	
    self.data = item
    self.prev = None
    self.next = None

위에 거를 그림으로 표현하면 아래와 같다.

dummy node 를 양방향에 두자

>> 데이터를 담고 있는 node 들은 모두 같은 모양이다

def __init__(self):
    self.nodeCount = 0
    self.head = Node(None)	#  dummy
    self.tail = Node(None)	#  dummy
    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:
        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(self, prev, newNode): 
    next = prev.next
    newNode.prev = prev
    newNode.next = next
    prev.next = newNode		# 링크 끊기
    next.prev = newNode		# 링크 끊기
    self.nodeCount += 1
    return True
    
리스트 마지막 원소에 삽입하면? 앞에서부터만 찾아가기 힘드므로 getAt 메소드 바꿔주기

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


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


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

 

insert 를 이해하니 이건 좀 쉬웠다.

 

이중연결리스트

def concat(self, L):
    self.tail.prev.next, L.head.next.prev = L.head.next, self.tail.prev
    self.tail = L.tail
    self.nodeCount += L.nodeCount
    
    # 마지막 tail이 더미 이기 때문에 더미에서 이전 링크로 온 후 넥스트를 
    # 그 다음 리스트 첫번째(dummy)의 next 로 해준다
    # 반대도 동일
    # 그림으로 보면 아래와 동일