[알고리즘 강의] 파트10. 양방향 연결 리스트(Doubly Linked Lists)

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

한 쪽으로만 링크를 연결하지 말고, 양쪽으로!

-> 앞으로도 (다음 node) 뒤로도 (이전 node) 진행 가능

 

양방향 연결 리스트

Node의 구조 확장

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

 

리스트 처음과 끝에 dummy node를 두자!

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

class DoublyLinkedList:
  def __init__(self, item):
    self.nodeCount = 0
    self.head = Node(None)
    self.tail = Node(None)
    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

 

특정 원소 얻어내기

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

 

원소의 삽입

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)

 

실습 과제1,2,3,4 - GitHub에서 확인

과제1. 양방향 연결 리스트 역방향 순회 (reverse 구현)

과제2. 양방향 연결 리스트 노드 삽입 (insertBefore() 구현)

과제3. 양방향 연결 리스트 노드 삭제 (popAfter(), popBefore(), popAt() 구현)

과제4. 양방향 연결 리스트의 병합 (concat 구현)

 

https://github.com/hanna56/Algorithm-lecture/tree/main

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.