자료구조3 - 연결 리스트 예제

자료구조2에서는 연결 리스트의 기본적인 기능을 구현해보았다.

이번 자료구조3에서는 연결 리스트를 이용한 2가지 예제에 대한 풀이를 진행하도록 하겠다.

(예제 문제는 엘리스 아카데미를 참고함)

 

 

class node:		# 연결 리스트를 구현할 노드 생성
    def __init__(self, data, ptr):  
        node.data = data    # 노드의 데이터를 초기화
        node.next = ptr     # 노드의 다음 노드를 가리키는 포인터를 초기화

class linkedpipe:
    def __init__(self):     # 연결 리스트 초기화
        self.start = None   # 연결 리스트의 시작점은 아직 정해지지 않음
        self.end = None     # 연결 리스트의 끝점도 아직 정해지지 않음

    def addLeft(self, n):   # 왼쪽에 노드 추가
        if self.start is None and self.end is None:     # 노드가 아예 없을 경우
            self.start = node(n, None)  # 시작노드와 끝노드를 새롭게 추가하는 노드로 변경
            self.end = node(n, None)
        else:
            new = node(n, self.start)  # 시작노드를 가리키는 n값의 노드를 추가
            self.start = new  # 시작노드가 새롭게 추가한 노드가 됨

    def addRight(self, n):  # 오른쪽에 노드 추가
        if self.start is None and self.end is None:
            self.start = node(n, None)
            self.end = node(n, None)
        else:
            self.end.next = node(n, None)   # 가장 마지막 노드가 새롭게 만든 노드를 가리키도록-
            self.end = node(n, None)    #가장 마지막 노드를 새롭게 만든 노드로 초기화

    def getBeads(self):     # 구슬의 위치를 리스트로 반환하는 함수
        beads = []
        current = self.start    #첫 번째 구슬부터 시작
        while current:  # 노드가 존재할 때까지 계속 
            beads.append(current.data)  # 리스트에 구슬을 추가
            current = current.next  # 다음 노드로 이동 

        return beads    # 리스트를 반환

 

 

class LinkedListElement : 	#노드를 정의하는 클래스
    def __init__(self, data, myPrev, myNext) :
        self.data=data
        self.myPrev=myPrev
        self.myNext=myNext
        
class orderManager :	#주문
    def __init__(self) :
        self.start=None
        self.end=None

    def addOrder(self, orderId) :
        order=LinkedListElement(orderId, None,None)
        if self.start==None and self.end==None: 	#만약 연결리스트에 아무 것도 없다면
            self.start=order
            self.end=order
        else:
            self.end.myNext=order 	#맨 마지막 노드가 가리키는 곳에 주문 추가
            order.myPrev=self.end
            self.end=order 	#맨 마지막 노드를 새롭게 추가한 주문으로 초기화

    def removeOrder(self, orderId) :
        if self.start==None and self.end==None:
            return
        else:
            current=self.start	#연결리스트의 처음 노드부터 탐색 시작
            while current != None:
                if current.data==orderId:
                    predata=current.myPrev
                    nextdata=current.myNext
                    if predata !=None:
                        predata.myNext=nextdata
                    if nextdata !=None:
                        nextdata.myPrev=predata
                    if current == self.end:  #삭제하려는 주문이 맨 마지막 주문일 경우
                        self.end=predata  #이중연결리스트의 마지막 주문을 이전 주문으로 바꿔주어야함
                    if current == self.start:  #삭제하려는 주문이 맨 앞 주문일 경우
                        self.start=nextdata  #이중연결리스트의 맨 앞 주문을 다음 주문으로 바꿔주어야함
                
                current=current.myNext #다음 노드로 이동


    def getOrder(self, orderId) :
        cnt=0
        current = self.start
        if self.start==None and self.end==None:
            return -1
        else:
            while current != None:
                cnt+=1
                if current.data == orderId:
                    return cnt
                else:
                    current=current.myNext
            return -1