연결 리스트(Linked Lists)

1 연결 리스트

• Node는 Data와 Link로 이루어져 있다. Link는 다음 노드로 이어진다
• Node 내의 데이터는 다른 구조로 이루어질 수 있다
  • 문자열, 레코드, 또 다른 연결 리스트 등
• 맨 첫 노드와 마지막 노드를 Head와 Tail로 지정한다
  • 원소를 추가할 때 tail을 알고 있는 것이 유리하다
• of nodes: 3, 처럼 몇 개의 노드가 있는지 알고 있는 것이 좋다

2 자료 구조 정의

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

class LinkedList:
		def __init__(self):
				self.nodeCount = 0
				self.head = None
				self.tail = None

3 연산 정의

3.1 특정 원소 참조 (k번째)

• 1부터 시작
• 알고리즘 구현에 있어 편하게 하기 위함

def getAt(self, pos):
		# 유효하지 않은 pos 필터링
		if pos <= 0 or pos > self.nodeCount:
				return None
			
		i = 1
		curr = self.head 
		# pos 탐색
		while i < pos:
				curr = curr.next
				i += 1
			
		return curr

3.2 리스트 순회

def traverse(self):
    res = []

    if self.nodeCount > 0: # 노드가 1개 이상 존재할 경우
        curr = self.head

        for _ in range(self.nodeCount) : # 현재 노드의 다음 노드가 존재한다면
            res.append(curr.data)
            curr = curr.next

    return res

3.3 길이 얻어내기

def getLength(self):
		return self.nodeCount

3.4 원소 삽입 (insertion)

• pos가 가리키는 위치에 newNode를 삽입하고 성공/실패에 따라 True/False를 리턴한다
  • 1 ≤ pos ≤ nodeCount+1
• 주의할 점
  • 삽입하려는 위치가 리스트 맨 앞일 때
    • prev가 없어짐 (head 앞의 노드는 없다)
    • Head 조정 필요
  • 삽입하려는 위치가 리스트 맨 끝일 때
    • Tail 조정 필요
  • 빈 리스트에 삽입할 때는 위 두 처리를 통해 자동으로 처리됨
• 시간복잡도
  • 맨 앞, 끝 삽입: O(1)
    • head, tail 때문
  • 중간에 삽입하는 경우 O(n)

def insertAt(self, pos, newNode):
		if pos < 1 or pos > self.codeCount + 1:
				return False
			
		if pos == 1: # 첫번째 노드로 넣고 싶은 경우
				newNode.next = self.head
				self.hand = newNode
			
		else:
				if pos == self.nodeCount+ 1: # 맨 끝 노드로 넣고 싶은 경우
						prev = self.tail
				else:
						prev = self.getAt(pos - 1)
				newNode.next = prev.next
				prev.next = newNode
		
		if pos == self.nodeCount + 1:
				self.tail = newNode
		prev = self.getAt(pos - 1)
		
		self.nodeCount += 1
		
		return True

3.5 원소 삭제하기(deletion)

• pos가 가리키는 위치의 node를 삭제하고 그 node의 데이터를 리턴
  • 1 ≤ pos ≤ nodeCount
• 주의사항
  1. 삭제하려는 node가 맨 앞의 것일 때
     • prev 없음
     • head 조정 필요
  2. 리스트 맨 끝의 node를 삭제할 때
     • Tail 조정 필요
     • 삭제하려는 node가 마지막 node일 때, → 즉 pos == nodeCount인 경우 prev를 찾을 방법이 없으므로 앞에서부터 찾아와야 한다
       
  3. 유일한 노드를 삭제할 때?
• 시간복잡도
  • 맨 앞에서 삭제하는 경우: O(1)
  • 중간, 맨 끝에서 삭제하는 경우: O(n)

def popAt(self, pos):
      if pos < 1 or pos > self.nodeCount:
          raise IndexError
          
      # 맨 앞 노드를 삭제할 경우
      if pos == 1:
          curr = self.head
          self.head = self.head.next
          
          # 유일한 노드일 경우
          if self.nodeCount == 1:
              self.tail = None
      
      # 2번째 이상인 노드를 삭제할 경우
      else:
          prev = self.getAt(pos - 1)
          
          curr = prev.next
          prev.next = curr.next
          
          # 마지막 노드를 삭제하는 경우 Tail 조정
          if pos == self.nodeCount:
              self.tail = prev
          
      self.nodeCount -= 1
      return curr.data

3.6 두 리스트 합치기 (concatenation)

• 연결 리스트 self의 뒤에 또다른 연결 리스트인 L을 이어 붙인다
• 주의사항
  • L(이어붙는 리스트)가 비었다면, tail이 None 이 될 수 있다

def concat(self, L):
		self.tail.next = L.head
		if L.tail:
				self.tail = L.tail
		self.nodeCount += L.nodeCount

4 배열과 비교한 연결 리스트

	배열	연결 리스트
저장 공간	연속한 위치	임의의 위치
특정 원소 지칭	매우 간편(인덱스)	선형탐색과 유사
특정 원소 지칭 시간복잡도	O(1)	O(n)

5 조금 변형된 연결 리스트 구조

• 연결 리스트는 삽입과 삭제가 유연하다는 장점을 갖는다
• 하지만 처음부터 n번째에 있는 노드를 찾는 과정은 부담이 될 수 있다
• 삽입과 삭제가 유연하다는 장점을 살리기 위해 연결 리스트를 조금 변형하고, 새로운 메소드 추가하자!

class LinkedList:
		def __init__(self):
				self.nodeCount = 0
				self.head = Node(None)
				self.tail = None
				self.head.next = self.tail

6 조금 변경된 연결 리스트의 연산 정의

• 더미노드를 활용함으로써 코드를 보다 깔끔하고 간결하게 작성할 수 있게된다

6.1 길이 얻어내기

• 달라진 점은 없다

def getLength(self):
		return self.nodeCount

6.2 리스트 순회

def traverse(self):
    result = []

    curr = self.head
    while curr.next:
		    curr = curr.next
		    result.append(curr.data)

    return result

6.3 특정 원소 참조 (k번째)

def getAt(self, pos):
		if pos < 1 or pos > self.nodeCount:
				return None
				
			i = 0 # 이전에는 1로 초기화했다
			curr = self.head
			while i < pos:
					curr = curr.next
					i += 1
			return curr

6.4 원소 삽입

1. insertAfter

   • prev가 가리키는 node의 다음에 newNode를 삽입하고 성공/실패에 따라 True/False를 리턴
   • 주의사항
     • Tail 뒤에 삽입할 경우

   def insertAfter(self, prev, newNode):
   		newNode.next = prev.next
   		
   		# Tail 뒤에 삽입할 경우
   		if prev.next is None:
   				self.tail = newNode
   				
   		prev.next = newNode
   		self.nodeCount += 1
   		return True

2. insertAt(self, pos, newNode)

   • 이미 구현한 insertAfter를 호출하여 이용하는 것으로 구현할 수 있다
   • pos를 통해 prev 노드를 구해 insertAfter()를 호출한다

   def insertAt(self, pos, newNode):
   		if pos < 1 or pos > self.nodeCount + 1:
   				return False
   				
   		if pos != 1 and pos == self.nodeCount + 1:
   				prev = self.tail
   		else:
   				prev = self.getAt(pos - 1)
   				
   		return self.insertAfter(prev, newNode)

6.5 원소 삭제

1. popAfter(self, prev):

   • prev의 다음 node를 삭제하고 그 node의 data를 리턴
   1. prev가 마지막 node일 때
      • 삭제할 node가 없어 None을 return한다
   2. 리스트 맨 끝의 node를 삭제할 때
      • tail 조정 필요

   def popAfter(self, prev):
       # prev가 마지막 node일 때
       if prev.next is None:
           return None
   
       curr = prev.next
       prev.next = curr.next
   
       # 마지막 노드인 경우 (tail 조정)
       if curr.next is None:
           self.tail = prev
   
       self.nodeCount -= 1
       return curr.data

2. popAt()

   1. popAfter를 호출하여 이용하는 것으로 구현 가능

   def popAt(self, pos):
       # pos 위치를 찾아서 그 위치인 노드를 삭제시키는 것
       # pos - 1, 즉 prev를 찾아서 popAfter 호출
       if pos < 1 or pos > self.nodeCount:
           raise IndexError
   
       if pos == 1:    # 함수 호출 횟수를 줄이기 위해
           prev = self.head
       else:
           prev = self.getAt(pos - 1)
   
       return self.popAfter(prev)

6.6 두 리스트 합치기

def concat(self, L):
		self.tail.next = L.head.next
		if L.tail:
				self.tail = L.tail
			self.nodeCount += L.nodeCount