[자료구조] 단일 연결 리스트 구현 (in python)

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

연결리스트의 기본 구조

• 데이터 필드와 하나 이상의 링크 필드로 구성된 노드가 연결된 형태
  => 노드 = 데이터 필드(해당 노드가 담고있는 data) + 링크 필드(다음 노드를 가리키는 link)

 

---

단일 연결 리스트

1. 단일 연결 리스트란 ?

• 노드들이 한 방향으로 연달아 연결되어 있는 구조
• head, tail 노드
  • head : 리스트의 첫 노드
  • tail : 리스트의 끝 노드

 

2. 단일 연결 리스트 구현

1) 노드 기본 구현

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

2) 단일 연결 리스트 연산 종류

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

3) 단일 연결 리스트 연산 구현

(1) 삽입 연산

• 두 가지 단계로 분류 가능
  • Step 1
    : 삽입될 노드의 앞 노드의 data값을 전달받으면 앞 노드를 찾아 노드가 어디에 삽입되어야 할지 탐색
  • Step 2
    : 위에서 찾은 노드가 삽입되어야 할 위치에 노드를 삽입
    • 삽입할 때 고려할 경우의 수
      • 아예 빈리스트인 경우
      • 앞 노드가 지정된 경우 (def insert에서 prev_data에 값이 할당된 경우)
      • 앞 노드가 None인 경우 (def insert에서 prev_data에 값이 할당되지 않은 경우 = 앞에 연결할 노드가 없다는 의미 = 맨 앞에 노드 추가 != 빈리스트)

• 코드 구현
  • Step 1 & 2

def find(self, item): # STEP 1
	# item : insert시에 삽입하는 리스트의 앞 노드 정보 (link말고 data로 줌)
	if not self.head: return None, None 
		# self.head가 없다 -> 빈리스트이니까 none, none 반환
		# 위의 if문을 충족하지 않으면 아래 코드를 실행
	temp = self.head 
		# self.head의 객체를 temp에 할당
	prev = None 
		# prev = None으로 정의하고
	while temp: 
	if temp.data == item: 
		# temp.data가 item과 동일하면 그때의 temp 객체가 삽입 노드의 앞 노드인 것
	return prev, temp 
		# temp의 앞노드인 prev, 그리고 삽입 노드의 앞 노드인 temp를 반환 => prev -> temp 이렇게 연결되어 있는 것
	prev = temp 
		# temp를 prev에 할당하고
	temp = temp.link 
		# 다음 리스트를 가리키는 temp.link를 temp로 할당
		return None, None 
			# 만약에 while문이 리스트가 tail에 이를때까지 돌아갔는데도 return값이 없었다 	
	# -> 앞 노드에 해당하는 것이 리스트에 없다는 의미이므로 None, None을 반환

def insert(self, prev_data, item): # STEP 2
	if self.head is None: 
  		# 공백리스트이면 당연히 head도 없고, tail도 없으니 -> 새로운 데이터가 포함되면 head = tail 성립
		node = Node(item) 
  			# 삽입할 데이터를 담은 리스트를 생성하고 (Node라는 클래스를 사용하여 만든 객체)
		self.head = node 
  			# self.head도 위에서 정의한 node 객체를 담고
		self.tail = node 
  			# self.tail도 위에서 정의한 node 객체를 담음
		return 
	node = Node(item) 
  		# self.head가 비어있지 않아도 node 객체 생성해야하니까
        # -> node = 삽입할 데이터의 값을 담은 노드니까 삽입노드
	if prev_data is None: 
  		# 입력받은 prev_data의 값이 None이면 리스트의 맨 앞에 노드를 삽입한다는 의미 
        # -> prev_data는 지금 삽입하는 연결리스트의 앞노드의 데이터값이 이거다를 지정해준 것 
        # -> prev_data = None이다 ? = 삽입할 노드 앞의 노드가 없다 = 리스트 젤 앞에 삽입하는거다
		node.link = self.head 
  			# self.head에 할당되어 있는 객체를 node의 link에 할당 (self.head를 node의 뒤로 연결시키는 것)
		self.head = node 
  			# 그리고 node 객체를 self.head에 할당해서 node를 headnode가 되도록 함
		return
	pprev, prev = self.find(prev_data) 
  		# 앞서 find함수에서 찾고 반환한 결과를 pprev, prev값으로 받음
        # : pprev -> prev -> node 순으로 연결될 예정
	if prev is None: 
  		# 근데 이렇게 했는데 만약에 이전 노드가 없었다하면
	print("Not Exist previous node") 
  		# 존재하지 않는다고 print
	return
else: 
  		# 아니면 = 이전 노드가 있었다면
	node.link = prev.link 
  			# 원래 prev가 가리키고 있던 리스트의 link를 node에게 연결
	prev.link = node 
  			# node를 prev.link에 연결
	if node.link is None: self.tail = node 
  			# 만약에 node에 링크가 할당되어 있지 않다 
              	= prev가 tail이었어서 할당해줄 link가 없었던 것 
                  	-> 그러니까 이제는 node가 tail이 됨

(2) 삭제 연산

• 삭제할 때 고려할 경우의 수
  • 앞노드가 None이 아닌 경우 (삭제할 노드의 앞 노드가 주어진 경우)
  • 앞노드가 None인 경우 (가장 앞의 노드를 삭제할 경우)

• 코드 구현

  def delete(self,item):
    if self.head is None: 
    	# 빈리스트이면
      print("Empty List")
      return
    prev, node = self.find(item) 
    	# 삭제할 데이터의 노드를 찾음 
        	-> node가 삭제할 데이터의 노드, prev는 삭제할 데이터 이전의 노드
    if node is None: 
    	# 찾아봤는데 삭제할 데이터의 노드가 존재하지 않으면 삭제할 것도 없지
      print("Not Exist node")
      return
    if prev: 
    	# prev가 존재하면
      prev.link = node.link 
      	# node가 연결하고 있는 다음 리스트를 prev.link에 할당해주고 node는 그 연결에서 빠져나옴
      print("Delete complitely")
    else: 
    	# prev가 존재하지 않으면
      if self.head == node: 
      	# 그리고 node가 head이면
        print("Head deleted") 
        self.head = node.link 
        	# 노드가 연결하고 있던 다음 리스트를 헤드로 지정하고 node는 그 연결에서 빠져나옴
    if node == self.tail: self.tail = prev 
    	# node가 tail이었으면 prev를 tail로 지정
    del node 
    	# 마지막으로는 node라는 리스트 삭제

(3) 리스트 길이 계산

• 기본 원리 : head에 연결된 노드부터 시작해서 link를 통해 하나씩 넘어가면서 count를 +1

• 코드 구현

  def length_list(self):
    count = 0
    temp = self.head
    while temp:
      count += 1
      temp = temp.link
    return count

(4) 리스트 연결

• 리스트 연결 경우의 수
  • 첫번째 리스트가 빈리스트이면 -> 두번째 리스트가 결과가 됨
  • 첫번째 리스트가 빈리스트가 아니면 -> 첫번째 리스트의 tail에 두번째 노드 head를 저장

• 코드 구현

  def concat(self, second): 
    if self.head is None: 
    	# 첫번째 리스트가 빈리스트인 경우
      return second
    elif second: 
    	# second가 빈리스트가 0이 아닌 경우
      temp = self.head 
      	# 첫번째 리스트의 self.head를 temp에 할당
      while temp.link:
        temp = temp.link 
        	# temp에 temp.link를 할당하면서 계속 다음 리스트로 넘어가다가 더이상 link값이 할당되지 않으면 stop 
            	-> 첫번째 리스트의 tail에 닿으면 stop
      temp.link = second 
      	# 연결할 second 리스트를 첫번째 리스트 tail의 링크에 할당
      while seconde.link: 
        second = second.link
        	# second 리스트를 대상으로 위의 과정 반복해서 second 리스트의 tail에 닿으면 stop
      self.tail = second
      	# second의 tail을 전체 리스트의 tail에 할당
    return self.head

(5) 역리스트

• 기본 원리
  
• 코드 구현

  def reverse(self):
    one = self.head 
    two = three = None
    self.tail = self.head # 역리스트를 만드는 과정이니까 head를 tail로
    while one:
      three = two 
      two = one
          # 연결리스트에 할당되면 three - two - one 이렇게 할당됨
        	= three가 셋 중 가장 앞 노드에 위치하고 one은 셋 중 가장 뒷 노드에 위치함
      one = one.link 
      	# one은 그 다음 노드로 넘어가고
      two.link = three 
      	# three를 two의 link에 할당
        	= 원래 연결 리스트에서 two는 three보다 뒤에 위치
            	-> 뒷 리스트의 링크에 앞 노드를 연결해주어 역순이 되도록 하는 것
    self.head = two 
    	# one이 None이다 
        	= 원래 리스트의 tail을 읽은 후 그 다음 노드를 읽지 못했다
            = two가 원래 연결리스트의 tail에 위치했을 때 while문 break
            -> 그래서 two가 head
        

(6) 전체 코드

class Node:
  def __init__(self, item):
    self.data = item
    self.link = None
  
class SinglyLinkedlist:
  def __init__(self):
    self.head = None
    self.tail = None
  
  def view(self):
    temp = self.head 
    	# temp라는 변수에 self.head(Node 클래스를 이용하여 생성한 객체 
        	+ 근데 비어있는게 아니라 앞선 내용이 포함되어 있음)라는 객체를 할당
    print('[', end = ' ')
    while temp: 
    	# 아래의 과정을 반복하다가 temp.link가 None일 때 
        	= self.tail에 도달해 더이상의 link가 존재하지 않을 때 STOP
      print(temp.data, end = ' ') 
      	# 가장 먼저는 self.head에 있는 데이터를 읽어오고 그 이후에 연결되어 있는 리스트들의 값을 
        연결된 순서대로 읽어옴 -> 어떻게 ?는 아래줄에
      temp = temp.link 
      	# temp.link라는 변수는 다음에 연결되어 있는 Node라는 클래스를 이용하여 만든 객체를 참조하고 있음 
        	-> 다음 리스트를 불러옴
    print(']', end= ' ')
    if self.head: 
    	# self.head 있으면 빈 리스트 아니니까 출력
      print('H = ', self.head.data, "T = ", self.tail.data)
    else:
      print("Empty list")
  
  def isEmpty(self):
    return not self.head
  
  def insert(self, prev_data, item): # 데이터 삽입
    if self.head is None: 
      node = Node(item) 
      self.head = node 
      self.tail = node 
      return 
    node = Node(item) 
    if prev_data is None: 
      node.link = self.head 
      self.head = node 
      return
    pprev, prev = self.find(prev_data) 
      print("Not Exist previous node") 
      return
    else: 
      node.link = prev.link 
      prev.link = node 
      if node.link is None: self.tail = node 
    
  def delete(self,item): # 데이터 삭제
    if self.head is None: 
      print("Empty List")
      return
    prev, node = self.find(item) 
    if node is None: 
      print("Not Exist node")
      return
    if prev: 
      prev.link = node.link 
      print("Delete complitely")
    else: 
      if self.head == node: 
        print("Head deleted") 
        self.head = node.link 
    if node == self.tail: self.tail = prev 
    del node
  
  def find(self, item): # 노드 찾기
    if not self.head: return None, None 
    temp = self.head 
    prev = None 
    while temp: 
      if temp.data == item: 
        return prev, temp 
      prev = temp 
      temp = temp.link
    return None, None 

  def length_list(self): # 길이 계산
    count = 0
    temp = self.head
    while temp:
      count += 1
      temp = temp.link
    return count
  
  def concat(self, second): # 리스트 연결
    if self.head is None:
      return second
    elif second:
      temp = self.head
      while temp.link:
        temp = temp.link
      temp.link = second
      while seconde.link:
        second = second.link
      self.tail = second
    return self.head

  def reverse(self): # 역 리스트
    one = self.head
    two = three = None
    self.tail = self.head
    while one:
      three = two
      two = one
      one = one.link
      two.link = three
    self.head = two