연결리스트 level 3 (Doubly Linked List)

3) 양방향(Doubly) 연결 리스트

  ① 양방향 연결 리스트 정의

    - 단반향 리스트와 달리 앞과 뒤(양방향)으로 리스트 접근이 가능하다

 

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

 

    - 삽입 및 정렬 연산에서 head 및 tail에서 연산할 시 리스트 처음과 끝에 Dummy Node를 둠으로써 양방향 연결 리스트를 형성한다

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)		
        self.tail = Node(None)		
        self.head.prev = None
        self.head.next = self.tail		# Doubly
        self.tail.prev = self.head		# Doubly
        self.tail.next = None

 

  ② 연결 리스트 연산

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

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None

	if pos > self.nodeCount // 2:				# 양방향으로 접근가능하기 때문
        i = 0
        curr = self.tail
        while i < self.nodeCount - pos + 1:
            curr = curr.prev
            i += 1
    else:
        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

    return curr​

    2. 리스트 순회 

def traverse(self):
    result = []
    curr = self.head
    while curr.next.next:		# 역방향 시 curr.prev.prev
        curr = curr.next		# 역방향 시 curr.prev
        result.append(curr.data)
    return result

    3. 길이 얻어내기

self.nodeCount()

    4. 원소 삽입

 

 

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
    
def insertBefore(self, next, newNode):
    prev = next.prev
    newNode.prev = prev
    newNode.next = next
    prev.next = newNode
    next.prev = newNode
    self.nodeCount += 1
    return True


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

	prev = self.getAt(pos - 1)
    return self.insertAfter(prev, newNode)

    5. 원소 삭제

def popAfter(self, prev):	# prev 에 의하여 주어진 node 의 다음에 있던 node 를 삭제
    result = 0
    curr = prev.next
    prev.next = curr.next
    curr.next.prev = prev
    result = curr.data
    self.nodeCount -= 1
    return result

def popBefore(self, next):	# next 에 의하여 주어진 node 의 이전에 있던 node 를 삭제
    result = 0
    curr = next.prev
    next.prev = curr.prev
    curr.prev.next = next
    result = curr.data
    self.nodeCount -= 1
    return result


def popAt(self, pos):		# pos 에 의하여 지정되는 node 를 삭제하고 그 node 에 담겨 있던 data item 을 리턴
    result = []
    if pos < 1 and pos > self.nodeCount : raise IndexError
     
    prev = self.getAt(pos - 1)
    next = self.getAt(pos + 1)
        
    result.append(self.popAfter(prev))
    result.append(self.popBefore(next))
        
    return result

    6. 두 연결 리스트의 연결

    def concat(self, L):
        self.tail.prev.next = L.head.next	# self 리스트 끝단 -> dummy Node
        L.head.next.prev = self.tail.prev
        self.tail = L.tail
        self.nodeCount += L.nodeCount