Python Double-LinkedList

johnque·2020년 2월 12일
0

Double-LinkedList

Double-LinkedList는 앞 뒤로 움직일 수 있는 리스트를 말함
일반적으로 head를 이용해 한 방향으로 밖에 이동할 수 없는 LinkedList와는 대조적임

양방향으로 이동하기 위해서는 왼쪽에는 Prev가, 오른쪽에는 Next가 있어야 하고, head뿐 아니라, tail도 있어야함

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

기존의 LinkedList에서 prev를 추가한 Node클래스를 작성

class DoubleLinkedList:
    def __init__(self, data):
    	self.head = Node(data)
        self.tail = self.head #tail과 head가 동일한 노드를 가리키도록 함

위처럼 해주는 이유는 처음에 생성된 Node는 처음이기도 하고 끝이기도 하기 때문
여기서 Node가 많이 삽입될수록, tail은 점점 그 Node를 따라가고, head는 맨 앞의 자기 자리를 지키기 때문에 값의 변경이 없음

아래 메소드들을 DoubleLinkedList 클래스 코드 안에 추가

Add last and first

def add_last(self, data):
    new = Node(data)
    new.prev = self.tail
    self.tail.next = new
    self.tail = new
    
def add_first(self, data):
    new = Node(data)
    new.next = self.head
    self.head.prev = new
    self.head = new

기본적인 틀은 그냥 LinkedList와 매우 비슷함
기존의 node와 새롭게 추가되는 newnext, prev를 적절히 잘 연결시켜주지 않으면 delete같은 메소드에 문제가 발생함
그걸 쉽게 도와주는게 바로 head, tail이니 적절히 활용

def delete(self, data):
    if self.head == '':
        return False
    if self.head.data == data:
        temp = self.head
        self.head = self.head.next
        del temp
    node = self.head
    while node.next:
        if node.next.data == data:
            temp = node.next
            node.next = node.next.next
            node.next.prev = node
            del temp
            return True:
        node = node.next
    return False

delete까지 구현하면 삽입 삭제가 전부 가능해짐
하지만 애초에 Double-LinkedList구현 목적은 양방향의 이동을 활용하는 점인데 아직 그게 등장하지 않았음

먼저 데이터를 정방향 그리고 역방향으로 출력하는 메소드

display and display Reverse

def display(self):
    node = self.head
    while node:
        print(node.data)
        node = node.next
        
def display_reverse(self):
    node = self.tail
    while node:
       print(node)
       node = node.prev

insert data from front, back

데이터를 앞에서부터 N번째 인덱스에 해당하는 Node 뒤에 데이터를 추가하는 방법

def getLength(self):
    node = self.head
    count = 0
    while node:
        node = node.next
        count += 1
    return count

먼저 연결리스트의 길이를 구하는 메소드 정의
위 방식처럼해도 되고 add할 때마다 count를 올려도 됨

def insert_front(self, n, data):
    if n == 0:
        add_first(data)
        return True
    elif n == self.getLength()-1:
        add_last(data)
        return True

    else:
        node = self.head.next
        count = 1
        while node.next and count < n:
            count += 1
            node = node.next
        if count < n:
            return False
        new = Node(data)
        new.next = node.next
        node.next.prev = new
        node.next = new
        new.prev = node
        return True

상) 앞에서 N번째 인덱스 뒤에 data를 삽입하는 메소드
하) 뒤에서 N번째 인덱스 앞에 data를 삽입하는 메소드

def insert_back(self, n, data):
    if n == 0:
        add_last(data)
        return True
    elif n == self.getLength()-1:
        add_first(data)
        return True

    else:
        node = self.tail.prev
        count = 1
        while node.prev and count < n:
            count += 1
            node = node.prev
        if count < n:
            return False
        new = Node(data)
        new.prev = node.prev
        node.prev.next = new
        node.prev = new
        new.next = node
        return True
profile
코딩의 고수가 되고 싶은 종한이

0개의 댓글