[Programmers] 4. 기본 자료구조: 연결리스트(Linked List) (3): 양방향 연결리스트 (Doubly Linked List)

illstandtall·2021년 4월 28일
0

Programmers dev course

목록 보기
5/34
post-thumbnail

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!


자료구조: 양방향 연결리스트 (Doubly Linked List)

  • 한 쪽으로만 링크를 연결하지 말고, 양쪽으로 연결하자는 아이디어 입니다.
  • 따라서 양쪽 모두 연결되어있는 리스트를 말합니다.
  • 양방향 연결리스트는 앞으로도 진행 가능하고 뒤로도 진행 가능합니다.

양방향 연결 리스트의 특징

  • 데이터 원소들을 차례로 방문할 때, 앞에서 부터 뒤로 진행할 수 있지만 뒤에서 앞으로 진행할 수도 있습니다.
  • 뒷 부분에 있는 노드에 더 빨리 접근할 수 있다는 것이 장점입니다.
  • 구현의 편의를 위해 더미노드를 headtail을 둡니다.

Python에서 연결리스트 Class로 구현

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


class DoublyLinkedList:
    def __init__(self):
        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

양방향 연결리스트의 연산 구현

1. k 번째 원소 참조

def getLength(self):
    return self.nodeCount

2-1.리스트 순회

def traverse(self):
    result = []
    curr = self.head
    while curr.next.next:
        curr = curr.next
        result.append(curr.data)
    return result
  • while의 조건만 바뀝니다. tail의 더미노드가 추가되었기 때문입니다.
  • 이 조건은 빈 리스트의 순회에서도 잘 적용됩니다.

2-2. 리스트 역순회

def reverse(self):
    result = []
    curr = self.tail
    while curr.prev.prev:
        curr = curr.prev
        result.append(curr.data)
    return result
  • 역순회도 할 수 있습니다. 리스트의 순회와 대칭적입니다.

3. 길이 얻어내기


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
  • 이전과 동일하게 코드를 짤 수도 있지만,
  • k 번째 원소가 앞쪽이면 앞에서 부터, 뒤쪽이면 뒤쪽에서 부터 순회를 해나가는 코드로 조금 더 개선되었습니다.

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 insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodeCount + 1:
        return False
    prev = self.getAt(pos - 1)
    return self.insertAfter(prev, newNode)
  • 양방향 연결 리스트에서는 이전과 다르게 이전 노드와 다음 노드의 prev, next를 조정해주어야 합니다.

5. 원소 삭제

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

        return curr.data

    def popAt(self, pos):
        if pos < 1 or self.nodeCount < pos:
            raise IndexError
            
        # call popAfter()
        prev = self.getAt(pos - 1)
        
        return self.popAfter(prev)

6. 두 리스트 합치기

    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

이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.

profile
주니어

0개의 댓글