자료구조 및 실습 - [4] 리스트 실습문제 (파이썬으로 구현하는 이중연결리스트, 이중연결리스트로 구현하는 다항식) (2)

이중연결리스트를 이용하여 영문자 리스트 ADT를 구현해보자.

 

파이썬을 활용해 이중연결리스트를 구현해보자. 혹시 자기가 파이썬의 클래스를 잘 모른다면 이번 코드가 잘 이해가 가지 않을 수 있다. 따라서 본인이 파이썬 클래스를 완벽하게 이해하지 못했다고 생각한다면

https://mainyoung.tistory.com/5

Python - 클래스 (Class) 1

위 글을 확인하자!

 

이중연결리스트를 구성하는 노드는 단일연결리스트를 구성하는 노드와 약간 다르다. 단일연결리스트의 노드는 다음 노드의 주소를 저장하는 next만 존재하지만, 이중연결리스트의 노드는 이전 노드를 연결하는 Prev가 존재한다. 또한 header 노드와 Trailer노드를 사용하면 작업의 편의성이 증진되므로, 이를 활용하여 이중연결리스트를 구현할 것이다.

이중연결리스트의 자세한 특징은

https://mainyoung.tistory.com/21

자료구조 및 실습 - [3] 기초 데이터 구조 (배열, 연결리스트) (1)

 

class Node(object): #이중연결 리스트의 Node의 구성요소는 data의 저장공간, 이전 노드 주소저장공간, 다음노드 주소 저장공간이 있다.
  def __init__(self, data,prev=None,next=None):
    self.data = data #data의 저장공간
    self.next = next #다음 연결된 노드
    self.prev = prev #이전 연결된 노드

class DList(object):
  def __init__(self):
    self.head = Node(None) #헤드노드 설정
    self.tail = Node(None,self.head) # data에는 None, prev에는 헤드노드와 연결
    self.head.next = self.tail #헤드노드의 next에는 tail노드 연결
    self.size=0 #리스트의 사이즈

  def listSize(self): #리스트의 사이즈를 반환
    return self.size

  def is_empty(self): #리스트의 사이즈가 0이면 True,아니면 False
    if self.size !=0:
      return False
    else:
      return True

  def selectNode(self, idx): #idx에 해당하는 노드를 선택한다.
    if idx> self.size: #만약 잘못된 인덱스가 입력되면?
      print("invalid position")

    else: #인덱스의 입력이 잘 되었을때
      if idx == 0:  #만약 인덱스가 0이면?
        return self.head  #헤드노드 반환
      if idx == self.size : #만약 인덱스가 맨 끝이면?
        return self.tail  # 테일노드 반환
      if idx <= self.size//2: #만약 인덱스값이 처음과 중간 사이에 있다면?
        target = self.head  #타겟을 헤드에 두고
        for _ in range(idx):  #idx만큼 for문을 돌면서
          target = target.next  #다음 노드로 넘어간다.
        return target
      else: #인덱스 값이 중간부터 끝까지 있다면?
        target = self.tail  #테일노드부터 시작해서
        for _ in range(self.size - idx): #인덱스까지 도달할때까지 for문을 돈다
          target = target.prev
        return target

  def appendleft(self, value):  #맨 앞쪽에 붙이는거
    if self.is_empty(): #값이 아예없으면
      self.head = Node(value) #노드 설정
      self.tail = Node(None,self.head) #헤드노드 연결
      self.head.next = self.tail  #헤드노드와 테일노드 연결
    
    else: # 리스트에 노드가 이미 있으면
      tmp = self.head #tmp에 헤드노드 저장해놓고
      self.head = Node(value,None,self.head) #헤드노드를 추가하는데, next에 기존 헤드노드였던것을 연결하면서 맨 왼쪽 리스트에 한개를 연결하게됨
      tmp.prev = self.head  #기존 헤드노드였던것의 이전 노드가 헤드노드로 설정

    self.size +=1 #사이즈 한개 추가

  def append(self,value): #맨 뒤쪽에 더하는거
    if self.is_empty(): #비어있으면 그냥 똑같이
      self.head = Node(value)
      self.tail = Node(None,self.head)
      self.head.next = self.tail

    else: 
      tmp = self.tail.prev #tmp에 꼬리노드의 prev를 저장해놓고
      newNode = Node(value,tmp,self.tail) #새로운 노드의 헤드
      tmp.next = newNode #꼬리노드는 냅두고 이 전에 노드를 하나 추가하는 방식 , 위에서는 헤드노드가 바뀌었지만 지금은 꼬리노드가 그대로임.
      self.tail.prev = newNode #왜냐면 꼬리쪽에 붙이는거는 인덱스로 봤을때 기존꼬리노드 뒤에 붙는게 아니라 꼬리는 그대로있고 그 앞에 붙기 때문 
    self.size +=1

  def insert(self,value,idx):
    if self.is_empty():#비어있으면
      self.head = Node(value) #헤드노드 설정
      self.tail = Node(None,self.head)#꼬리노드 설정, 헤드와 연결
      self.head.next = self.tail #꼬리와 헤드와 연결

    else:#아니면
      tmp  = self.selectNode(idx) #tmp에 기존 노드저장하고
      if tmp == None:
        return
      if tmp == self.head: #인덱스가 헤드노드라면
        self.appendleft(value) # 아까 설정한거
      elif tmp == self.tail:#테일노드라면
        self.append(value) #append
      else:#그 외
        tmp_prev = tmp.prev #기존 idx에 해당하는 prev를 저장하고
        newNode = Node(value,tmp_prev,tmp) #new Node를 생성하는데 prev에는 tmp_prev,tmp에는 기존 idx에 있던 tmp를 연결
        tmp_prev.next = newNode #tmp_prev의 next에는 new node연결
        tmp.prev = newNode # tmp의 prev에는 newNode연결

    self.size +=1
  
  def delete(self, idx): 
    if self.is_empty(): #노드가 없으면
      print("invalid position")
      return
    else:
      tmp = self.selectNode(idx) #노드를 선택하고
      if tmp == None: #만약 노드가 없으면...
        return
      elif tmp == self.head: #헤드 노드면?
        tmp = self.head #tmp에 헤드노드 저장
        self.head = self.head.next #헤드노드를 헤드의 다음노드로 연결
      elif tmp == self.tail : #꼬리노드면?
        tmp = self.tail
        self.tail = self.tail.prev #꼬리노드를 꼬리이전 노드로 연결
      else: #중간에잇다면?
        tmp.prev.next = tmp.next #선택된 노드의 이전노드의 next에는 tmp.next연결
        tmp.next.prev = tmp.prev #선택된 다음 노드의 이전에는 tmp.prev연결
      
      del(tmp) #그리고 tmp삭제
      self.size -=1 #개수 삭제

  def printlist(self): #리스트 프린트하기
    target = self.head # 헤드노드부터
    while target != self.tail: #꼬리노드까지
      if target.next != self.tail: #만약 노드의 next에 연결된게 꼬리노드가 아니면
        print(target.data,'<=>',end ='') #출력
      else:
        print(target.data) #꼬리노드면 데이터만 출력
      
      target = target.next #계속 이어가기

먼저 Node에 대한 Class를 구성한다. 이중연결리스트의 노드는 이전 노드를 연결하는 Prev와 다음 노드를 연결하는 next, 원소를 저장하는 data를 만들어 주었다.

 

또한 DList Class를 정의하며 이중연결리스트를 구현했다. 자세한 설명은 코드를 짜며 주석을 읽어보는 것을 추천한다.

위 코드는 구글링을 하며 어디선가 비스무리하게 베껴온 코드이다.

 

따라서 나만의 이중연결리스트를 구현하고자 의사코드만 참고하여 이중연결리스트를 구현했다.

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

class DList(object):
  # 이중연결리스트 초기화
  def __init__(self): 
    self.header = Node(None)
    self.trailer = Node(None,self.header)
    self.header.next = self.trailer
    self.listsize = 0
  # get
  def get(self,rank):
    if rank<1 or self.listsize<rank:
      print("Invalid position")
    else:
      target = self.header
      for i in range(rank):
        target = target.next
      print(target.data)
      return target.data
  #순회 (모든 연결 리스트 원소 출력)
  def printlist(self):
    if self.listsize ==0:
      print("")
    else:
      target = self.header.next
      while target != self.trailer:
        print(target.data, end=" ")
        target = target.next
  
  #삽입 
  # def addNodeBefore(self,pnode,data):
  #   newNode = Node(data)
  #   newNode.prev = pnode.prev
  #   newNode.next = pnode
  #   pnode.prev.next = newNode
  #   pnode.prev = newNode

  def addNode(self,rank,data):
    if rank<1 or rank>self.listsize+1:
      print("Invalid position")
    else:
      target = self.header
      for i in range(rank):
        target = target.next
      newNode = Node(data)
      newNode.prev = target.prev
      newNode.next = target
      target.prev.next = newNode
      target.prev = newNode
      self.listsize +=1
  
  #삭제 
  # def removeNode(self,pnode):
  #   data = pnode.data
  #   pnode.prev.next = pnode.next
  #   pnode.next.prev = pnode.prev
  #   del(pnode)
  #   return data

  def remove(self,rank):
    if rank<1 or self.listsize<rank:
      print("Invalid position")
    else:
      target = self.header
      for i in range(rank):
        target = target.next
      data = target.data
      target.prev.next = target.next
      target.next.prev = target.prev
      del(target)
      self.listsize -=1
      print(data)

 

 

다항식을 헤더 단일연결리스트로 표현해보자.

다항식을 표현하는 연결리스트 구조는 다음과 같다.

- 하나의 다항식(polynomial)을 하나의 헤더 단일연결리스트로 표현하는 방식 사용

 

또한 다항식의 각 항은 하나의 노드로 표현하고, 각 노드에는 다음 세 개의 필드를 저장한다. 

- Coef : 항의 계수

- Exp: 항의 계수

- next : 다음 노드를 가리키는 링크

 

하나의 연결리스트의 각 노드는 차수의 내림차순 순으로 유지하고, 계수가 0인 항의 노드는 유지하지 않음

 

다항식에 항 추가

기존 다항식의 마지막 항을 표현하는 노드 k에 계수 c와 차수 e로 이루어진 새 항 추가

'다항식에 항 추가' 의사코드

다항식 덧셈

두 개의 다항식 x, y에 대한 덧셈을 수행하여 그 결과를 새로운 헤더 단일연결리스트에 저장
- 예: 위 예의 다항식 a, b의 덧셈 결과는 3x4 + 11x3 + 4 를 반환

위를 참고하여 다항식의 덧셈을 단일연결리스트로 정의했다.

# 다항식 단일연결리스트 정의
class Node:
  def __init__(self,coef,exp,next = None):
    self.coef = coef
    self.exp = exp
    self.next = next

class polynomials:
  def __init__(self): #초기화
    self.header = Node(None,None)
    self.polysize = 0

  def appendTerm(self,coef,exp):
    newnode = Node(coef,exp)
    newnode.coef = coef
    newnode.exp = exp

    target = self.header

    if self.polysize == 0:
      self.header.next = newnode
    else:
      for _ in range(self.polysize):
        target = target.next
      target.next = newnode
    self.polysize +=1
    
#========================================================================

result = polynomials()
x = polynomials()
y = polynomials()

N = int(input())
a = list(map(int,input().split()))
M = int(input())
b = list(map(int,input().split()))

tmp = 0
for i in range(N):
  x.appendTerm(a[tmp],a[tmp+1])
  tmp+=2

tmp = 0
for i in range(M):
  y.appendTerm(b[tmp],b[tmp+1])
  tmp+=2

i = x.header.next
j = y.header.next
while (i!=None) and (j != None):
  if i.exp>j.exp:
    result.appendTerm(i.coef,i.exp)
    i = i.next
  elif i.exp<j.exp:
    result.appendTerm(j.coef,j.exp)
    j = j.next
  else:
    sum = i.coef + j.coef
    if sum != 0:
      result.appendTerm(sum,i.exp)
      i = i.next
      j=j.next

while(i!=None):
  result.appendTerm(i.coef,i.exp)
  i = i.next

while(j!=None):
  result.appendTerm(j.coef,j.exp)
  j = j.next
  
  
target = result.header
for _ in range(result.polysize):
  target = target.next
  print(target.coef,target.exp,end=' ')

>>> 3 # N
>>> 5 3 3 2 3 1 # 첫번째 다항식
>>> 3 # M
>>> 2 6 2 3 1 0 # 두번째 다항식

2 6 7 3 3 2 3 1 1 0

다항식의 덧셈이 잘 수행되는것을 확인할 수 있다.