[자료구조] 원형 리스트, 이중 리스트 구현 (in python)

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님

원형 리스트

1. 원형 리스트란 ?

• 단일 리스트에서의 마지막 노드가 맨처음 노드와 연결된 형태
• 마지막 노드의 link가 NULL이 아님
• head가 변경되어도 연결리스트를 유지할 수 있음

 

2. 원형 리스트 구현

1) 노드 기본 구현

class Node:
  def __init__(self, item):
    self.data = item
    self.link = None

2) 원형 연결 리스트 연산 종류

• 삽입 연산
• 삭제 연산
• 리스트 길이 계산

3) 원형 연결 리스트 구현

(1) 삽입 연산

• 삽입 연산의 경우의 수 세 가지
  • 빈리스트에 삽입하는 경우
  • 리스트 맨 앞 위치로 삽입하는 경우
  • 리스트 중간(OR 끝)에 삽입하는 경우
    
    
• 코드 구현1 - 빈리스트에 삽입하는 경우 
  • 삽입되는 노드가 head이면서 tail
  • 원형 연결 리스트에서는 노드가 한 개일때 자기 자신을 연결

if self.head is None: 
    # head노드가 없다 = 빈리스트이다 -> 빈리스트이면
  self.head = node 
    # 삽입된 노드는 head노드이면서
  self.tail = node
    # tail 노드이기도 하다
  node.link = self.head
    # self.head를 node의 link가 연결하도록 해서 node가 
    자기 자신을 순환하는 원소가 한 개인 연결리스트가 될 수 있도록
  return

• 코드 구현2 - 리스트 맨 앞 위치로 삽입하는 경우
  • 원래의 head를 삽입 노드의 link에 연결
  • 삽입 노드를 head로 지정

elif prev is None:
	# 앞 노드가 없다 = 리스트의 맨 앞에 노드를 삽입하면 된다
	node.link = self.head
		# 원래의 head 노드를 삽입 노드의 link에 연결한 뒤
	self.head = node
		# node를 head노드로 지정
	return

• 코드 구현3 - 리스트 중간(OR 끝)에 삽입하는 경우
  • 삽입할 노드의 앞 노드를 찾고
  • 없으면 그대로 STOP / 있으면 KEEP GOING
  • node의 링크에 앞 링크를 저장
  • 앞노드의 링크에는 node를 저장
  • 만약 앞노드의 link가 head와 연결되어 있으면 = 앞노드가 tail 노드다 -> node가 tail 노드

pprev, prev = self.find(prev) 
	# prev값이 None이 아니었다면 prev값을 찾아보자
if prev is None: 
	# 찾아봤는데도 리스트 안에 prev값이 존재하지 않으면
		print("Not Exist previous node")
		return
else:
	# prev값이 실제로 리스트 안에 존재하면
	if prev.link == self.head: self.tail = node
		# prev의 link에 head가 연결되어 있다는건 prev가 tail 노드였다는 의미 -> node를 tail 노드로
	node.link = prev.link 
		# prev의 link를 node의 link에 연결한 뒤
	prev.link = node
		# node를 prev.link에 연결해줌

(2) 삭제 연산

• 삭제 연산의 경우의 수
  • 삭제 노드가 head 노드
  • 삭제 노드가 tail 노드
  • 삭제 노드가 중간 어딘가의 노드
• 코드 구현

  def c_delete(self, item):
    if self.head is None: 
        # head 노드 없다 = 빈리스트다
      print("Empty List")
      return
    prev, node = self.find(item)
      # 삭제할 node 찾고
    if node is None:
        # 삭제할 노드가 리스트 내부에 존재하지 않으면
      print("Non Exist node")
      return
    if prev:
        # prev가 존재하면
      prev.link = node.link
        # prev의 링크에 삭제할 노드가 연결하고 있던 노드를 연결시켜주고
      if self.tail == node : self.tail = prev
        # 그 노드가 tail이었으면 전 노드가 tail이 됨
      print("Delete complitely")
    else:
        # 삭제할 노드가 맨 앞의 값이다
      if self.head == node:
        # 노드가 head였으면
        self.head == node.link
          # node가 연결하고 있던 노드를 head 노드로 만들어주고
        print("Head delete")
      if self.tail == node:
        # node가 tail 이었으면 -> 한개의 노드만 있었다면
        self.tail = self.head
          # head, tail 연결 -> 빈리스트
    del node
      # 노드 삭제

(3) 리스트 길이 계산

• 코드 구현

  def length_list(self):
    if not self.head : return 0
    count = 0
    temp = self.head
    while temp.link:
      count += 1
      temp = temp.link
      if temp == self.head : break
      	# 한바퀴 다 돌아서 head노드로 다시 돌아오면 break

+) 원형 리스트에서 원소 찾는 함수

... 내가 코드 짜서 틀린 부분 있을지도 몰루 ...

  def find(self, item):
    temp = self.head
    prev = None
    c = 0
    while temp:
      if temp.data == item:
        return prev, temp
      prev = temp
      temp = temp.link
      c += 1
      if temp == self.head:
        print(c)
        return None, None

4) 전체 코드

class Node:
  def __init__(self, item):
    self.data = item
    self.link = None

class Circularlist:
  def __init__(self):
    self.head = None
    self.tail = None
  
  def isEmpty(self):
    return not self.head
  
  def length_list(self):
    if not self.head : return 0
    count = 0
    temp = self.head
    while temp.link:
      count += 1
      temp = temp.link
      if temp == self.head : break
    return count
  
  def add_rear(self, item): # 노드를 끝에만 추가하는 함수
    node = Node(item)
    if self.head is None:
      self.head = node
      self.tail = node
    else:
      self.tail.link = node
      self.tail = node
    node.link = self.head
  
  def view(self):
    temp = self.head
    print('[', end = ' ')
    if self.head == self.tail:
      print(temp.data, end = ' ')
    else:
      while self.head != self.tail:
        print(temp.data, end = ' ')
        temp = temp.link
        if temp is self.head : break
    print(']', end = ' ')
    if self.head:
      print("H = ", self.head.data, "T =", self.tail.data)
    else:
      print("Empty list")

  def c_insert(self, prev, item): # 어디든 노드를 추가할 수 있는 함수
    node = Node(item)
    if self.head is None: 
      self.head = node 
      self.tail = node
      node.link = self.head
      return
    elif prev is None:
      node.link = self.head
      self.head = node
      return
    pprev, prev = self.find(prev) 
    if prev is None: 
      print("Not Exist previous node")
      return
    else:
      if prev.link == self.head: self.tail = node
      node.link = prev.link 
      prev.link = node
      
  def c_delete(self, item):
    if self.head is None: 
      print("Empty List")
      return
    prev, node = self.find(item)
    if node is None:
      print("Non Exist node")
      return
    if prev:
      prev.link = node.link
      if self.tail == node : self.tail = prev
      print("Delete complitely")
    else:
      if self.head == node:
        self.head == node.link
        print("Head delete")
      if self.tail == node:
        self.tail = self.head
    del node
  
  def find(self, item):
    temp = self.head
    prev = None
    c = 0
    while temp:
      if temp.data == item:
        return prev, temp
      prev = temp
      temp = temp.link
      c += 1
      if temp == self.head:
        print(c)
        return None, None

 

---

이중 연결 리스트

1. 이중 연결 리스트란 ?

• 노드의 왼쪽, 오른쪽에 link가 존재해서 이중으로 연결되어 있음
• 이중 연결 리스트의 head는 앞선 head 노드와는 의미가 다름
• head 노드 : 노드의 개수를 저장, 삭제는 안됨

2. 이중 연결 리스트 구현

1) 기본 노드 구현

: 앞선 예제들과 기본 노드 구현부터 차이가 있음 -> llink, rlink 따로 존재

class Node:
  def __init__(self, item):
    self.data = item
    self.rlink = None
    self.llink = None

2) 이중 연결 리스트 연산 종류

• 삽입 연산
• 삭제 연산

3) 코드 구현

• 삽입 연산 구현
  • 삽입 순서 중요

  def insertDLL(self, prev, item):
    node = Node(item)
    self.head.data += 1
    	# 데이터 개수 + 1
    if self.isEmpty():
    	# 리스트가 비어있으면 헤드와 삽입 노드가 완전히 연결
      node.llink = self.head
      node.rlink = self.head
      self.head.rlink = node
      self.head.llink = node
    else:
      prev = self.find(prev)
      	# 앞노드의 값 찾아서 앞노드를 반환
      if prev is None:
      	# 아무것도 안찾아지면
        print(" Not exist previous node data")
        return
      # 바로 아래 두 줄은 순서가 바뀌어도 상관없음
      node.llink = prev
      	# 앞노드를 node의 왼쪽 link에 연결
      node.rlink = prev.rlink
      	# 앞노드가 오른쪽 link로 연결하고 있던 뒷노드의 link를 삽입노드의 오른쪽 link에 연결 
      # 여기 바로 아래 두 줄의 순서가 매우 중요 !!!!!!
      prev.rlink.llink = node
      	# 앞노드의 오른쪽 link가 연결하고 있던 노드의 왼쪽 link에 노드를 연결한 "뒤"
      prev.rlink = node
      	# node를 앞노드의 오른쪽 link에 연결
      ```
  

• 삭제 연산 구현
  • head는 삭제 불가

   def deleteDLL(self, item):
     if self.isEmpty():
       print("Empty List")
       return
     node = self.find(item)
     	# 삭제하려는 노드 찾아서
     if not node:
       print("not exist node")
       return
     if self.head == node:
     	# 노드가 head이면 삭제 불가
       print("head cannot be deleted")
       return;
     self.head.data -= 1
     	# 리스트 개수 -1 해주고
     node.rlink.llink = node.llink
     	# 삭제할 노드 뒤에 있는 노드의 왼쪽 링크에 삭제할 노드 앞의 노드를 연결
     node.llink.rlink = node.rlink
     	# 앞노드의 오른쪽 링크에 삭제할 노드 뒷 노드를 연결
     del node
     	# 삭제
  		```

4) 전체 코드

class Node:
  def __init__(self, item):
    self.data = item
    self.rlink = None
    self.llink = None

class DLinkedlist:
  def __init__(self):
    self.head = Node(0)
    self.head.rlink = self.head
    self.head.llink = self.head
  
  def view(self):
    temp = self.head.rlink
    print('[', end = ' ')
    while temp != self.head:
      print(temp.data, end = ' ')
      temp = temp.rlink
    print(']', end = ' ')
    if not self.isEmpty():
      print("H=", self.head.data, "R=", self.head.rlink.data, "L=",self.head.llink.data)
    else: print("Empty list")
  
  def isEmpty(self):
    return self.head.rlink == self.head
  
  def insertDLL(self, prev, item):
    node = Node(item)
    self.head.data += 1
    if self.isEmpty():
      node.llink = self.head
      node.rlink = self.head
      self.head.rlink = node
      self.head.llink = node
    else:
      prev = self.find(prev)
      if prev is None:
        print(" Not exist previous node data")
        return
      node.llink = prev
      node.rlink = prev.rlink
      prev.rlink.llink = node
      prev.rlink = node

  def deleteDLL(self, item):
    if self.isEmpty():
      print("Empty List")
      return
    node = self.find(item)
    if not node:
      print("not exist node")
      return
    if self.head == node:
      print("head cannot be deleted")
      return;
    self.head.data -= 1
    node.rlink.llink = node.llink
    node.llink.rlink = node.rlink
    del node
  
  def find(self, item):
    temp = self.head.rlink
    while temp != self.head:
      if temp.data == item:
        return temp
      temp = temp.rlink
    return None