이번에는 연결리스트의 마지막 포스팅을 하도록 하겠습니다!!

연결 리스트(Linked Lists) (3)

연결 리스트가 힘을 발휘할 때

• 아이폰 실행중인 어플 화면
• 삽입과 삭제가 유연하다는 것이 가장 큰 장점

빠른 연결 리스트

연결 리스트를 조금 더 빠르게 사용하기 위한 새로운 메서드

• insertAfter(prev, newNode)
• popAfter(prev)
  • 위 두 메소드는 prev를 사용한다.
  • 하지만 맨 앞 노드의 경우 prev가 존재하지 않는다.
  • 위 문제를 해결하기 위해 연결 리스트를 확장한다.
  • 맨 앞에 dummy node(기능은 하지 않고 자리만 잡혀있는 node)를 추가한 형태로 확장

class LinkedList:
	def __init__(self):
    	self.nodeCount = 0
        self.head = Node(None) # 비어있는 dummy node 추가
        self.tail = None
        self.head.next = self.tail

연산 정의

1. 길이 얻어내기
2. 리스트 순회
3. 특정 원소 참조 (k 번째)
4. 원소 삽입
5. 원소 삭제
6. 두 리스트 합치기

원소의 삽입

def insertAfter(self, prev, newNode):

• prev가 가리키는 node의 다음에 newNode를 삽입하고 성공/실패에 따라 True/False를 리턴
• L.insertAfter(prev, newNode):

def insertAfter(self, prev, newNode):
	newNode.next = prev.next
    prev.next = newNode
    self.nodeCount += 1
    return True

코드 구현 시 주의사항

• tail에 새로운 노드가 추가되는 경우
• tail도 새로운 node를 가리키게 되어야한다.

def insertAfter(self, prev, newNode):
	newNode.next = prev.next
    if prev.next is None:
    	self.tail = newNode
    prev.next = newNode
    self.nodeCount += 1
    return True

insertAt의 구현
def insertAt(self, pos, newNode):

• 이미 구현한 insertAfter()를 호출하여 이용
  (1) pos 범위 조건 확인
  (2) pos == 1인 경우에는 head 뒤에 새 node 삽입
  (3) pos == nodeCount+1 인 경우는 prev <- tail
  (4) 그렇지 않은 경우에는 prev <- getAt(..)z

원소의 삭제

def popAfter(self, prev):

• prev의 다음 node를 삭제하고
• 그 node의 data를 리턴
• r = L.popAfter(prev)
• prev / curr / next
• prev의 next는 curr의 next
• curr의 data retrun

코드 구현 시 주의사항
(1) prev가 마지막 node 일 때, (prev.next == None)

• 삭제할 node 없다.
• return None
  (2) 리스트 맨 끝의 node를 삭제할 때. (curr.next == None)
• tail 조정 필요

두 리스트의 연결

• self.tail.next = L2.head.next
• tail의 next에 head의 next를 연결 (head는 비어있다.)
• self.tail = L2.tail

연결 리스트 연산

class Node:

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


class LinkedList:

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


	def __repr__(self):
		if self.nodeCount == 0:
			return 'LinkedList: empty'

		s = ''
		curr = self.head
		while curr.next:
			curr = curr.next
			s += repr(curr.data)
			if curr.next is not None:
				s += ' -> '
		return s


	def getLength(self):
		return self.nodeCount


	def traverse(self):
		result = []
		curr = self.head
		while curr.next:
			curr = curr.next
			result.append(curr.data)
		return result


	def getAt(self, pos):
		if pos < 0 or pos > self.nodeCount:
			return None

		i = 0
		curr = self.head
		while i < pos:
			curr = curr.next
			i += 1

		return curr


	def insertAfter(self, prev, newNode):
		newNode.next = prev.next
		if prev.next is None:
			self.tail = newNode
		prev.next = newNode
		self.nodeCount += 1
		return True


	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)


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