파이썬 이중연결리스트에 대한 예시, 답변 (해답)

class DList:
    class Node:
        def __init__(self, item, prev, link):
            self.item = item
            self.prev = prev
            self.next = link

    def __init__(self):
        self.head = self.Node(None, None, None)
        self.tail = self.Node(None, self.head, None)
        self.head.next = self.tail
        self.size = 0

   def size(self):
        return self.size()

    def is_empty(self):
        return self.size == 0


   def insert_after(self, p, item):
        t = p.next
        n = self.Node(item, p, t)
        t.prev = n
        p.next = n
        self.size += 1
# add 작성 완료
   def add(self, pos, item):
        p = self.head
        for k in range(pos):
            p = p.next
        t = p.prev
        n = self.Node(item, t, p)
        p.prev = n
        t.next = n
        self.size += 1
# delete 미완성
   def delete(self,x):
        p = self.head
        for k in range( ):
            p = p.next
        f = x.prev
        r = x.next
        f.next = r
        r.prev = f
        self.size -= 1
     return x.item
# get 미완성
    def get(self,target):
      
# print 완료
 def print_list(self):
        if self.is_empty():
            print('리스트 비어있음')
        else:
            p = self.head.next
            while p != self.tail:
                if p.next != self.tail:
                    print(p.item, end='')
                else:
                    print(p.item)
                p = p.next


class EmptyError(Exception):
    pass

# 메인함수 add 호출 A와 print_list호출 P 완성
# get ->G delete->D 미완성
if __name__ == '__main__':
s = DList()
num=int(input())
for i in range(num):
inputs=input().split(" ")
operation=inputs[0]
if operation=="A":
pos=int(inputs[1])
alphabet=inputs[-1]
s.add(pos,alphabet)
elif operation=="P":
s.print_list()
조건설명
A:add(r,e):list순위 r에 원소 e 추가
D:delete(r):list순위 r에 위치한 원소 삭제
G:get(r):list의 순위 r에 위치한 원소 반환
P:print():list의 모든 원소를 저장 순위대로 공백 없이 출력
순위 정보가 유효하지 않으면 invalid position 출력, 해당연산 무시
각 연산의 내용이 연산의 종류, 순위(양의정수), 원소(영문자) 순서로 입력

1.
5 A 1 S
A 2 t
A 3 r
A 3 a
Star
를 완성시키기 위해서
def insert_before(self, p, item):
    t = p.prev
    n = self.Node(item, t, p)
    p.prev = n
    t.next = n
    self.size += 1
를
def add(self, pos, item):
        p = self.head
        for k in range(pos):
            p = p.next
        t = p.prev
        n = self.Node(item, t, p)
        p.prev = n
        t.next = n
        self.size += 1
로 바꿨어요.
2.
9
A 1 D
A 2 a
A 3 y
D 1
P         ->ay
G 3       ->invalid position
A 1 S
P        ->Say
G 3      ->y

이렇게 출력되기 위해서 저 코드들을 어떻게 변경,작성해야하는지 모르겠어요.

 

 

==================================================

[답변]

 

insert_before() 메소드 구현
add() 메소드에서 사용하는 insert_before() 메소드가 구현되어 있지 않은데, 이것을 구현해야 합니다. insert_before() 메소드는 주어진 노드 p의 앞에 새로운 노드를 삽입하는 메소드입니다.

 

def insert_before(self, p, item):
    t = p.prev
    n = self.Node(item, t, p)
    p.prev = n
    t.next = n
    self.size += 1

add() 메소드 구현
add() 메소드는 주어진 순위에 새로운 노드를 삽입하는 메소드입니다. 우선 리스트의 처음 노드를 가리키는 head 노드부터 시작하여, 주어진 순위에 도달할 때까지 노드를 이동합니다. 그리고 해당 순위에 새로운 노드를 삽입하면 됩니다. 새로운 노드를 삽입할 때는 insert_before() 메소드를 사용하면 됩니다.

 

 

def add(self, pos, item):
    if pos < 1 or pos > self.size + 1:
        print("invalid position")
        return
    
    p = self.head
    for k in range(pos):
        p = p.next
    self.insert_before(p, item)

 

delete() 메소드 구현
delete() 메소드는 주어진 노드를 삭제하는 메소드입니다. 주어진 노드의 이전 노드와 다음 노드를 찾은 후, 이전 노드의 next 필드와 다음 노드의 prev 필드를 연결해주면 됩니다.

 

def delete(self, x):
    if x == None or x == self.head or x == self.tail:
        raise EmptyError("삭제할 수 없음")
    else:
        x.prev.next = x.next
        x.next.prev = x.prev
        self.size -= 1
        return x.item

 

 

get() 메소드 구현
get() 메소드는 주어진 순위에 해당하는 노드의 값을 반환하는 메소드입니다. 순위가 유효하지 않으면 "invalid position"을 출력하고, 유효한 순위이면 해당 노드의 값을 반환합니다.

 

def get(self, target):
    if target < 1 or target > self.size:
        print("invalid position")
        return None
    
    p = self.head
    for i in range(target):
        p = p.next
    return p.item

 

메인 함수 구현
마지막으로, 주어진 연산을 수행하는 메인 함수를 작성해야 합니다.

 

if __name__ == '__main__':
    s = DList()
    num = int(input())

    for i in range(num):
        inputs = input().split()
        operation = inputs[0]

        if operation == "A":
            pos = int(inputs[1])
            alphabet = s.add(pos, alphabet)

    elif operation == "D":
        pos = int(inputs[1])
        x = s.head
        for i in range(pos):
            x = x.next
        s.delete(x)

    elif operation == "G":
        pos = int(inputs[1])
        print(s.get(pos))

    elif operation == "P":
        s.print_list()

위와 같이 구현하면 입력에 따라 리스트에 노드를 추가, 삭제, 값을 반환하고, 전체 리스트를 출력하는 기능을 수행할 수 있습니다. 다만, `add()` 메소드에서 순위가 유효하지 않은 경우 "invalid position"을 출력하고, `delete()` 메소드에서 삭제할 노드가 유효하지 않은 경우 `EmptyError` 예외를 발생시켰습니다. 이 부분은 필요에 따라 수정하셔도 됩니다.

 

 

 

 

* 개인적으로 초심자,  중급자에게 추천하는 파이썬 책은 렛츠기릿 파이썬 입니다. 

예제가 창의적이고 단계별로 따라하기 쉬워요 

중반 이후부터는 데이터로 그래프도 그릴 수 있으니 파이썬 공부하시는 분들 꼭 해보세요 !

* 무료 유튜브 강의도 제공되니 참고하세요



http://www.yes24.com/Product/Goods/102418815

Let’s Get IT 파이썬 프로그래밍 - YES24

 

https://www.youtube.com/watch?v=rdeQ8wAlUt8&list=PLLw0tS0APN1w4ZBNdT0mVMu0CY3WETfUD