연결리스트 (2)

연결리스트는 삽입과 삭제가 유연하다는 것이 가장 큰 장점이다.

(1)에서는 특정번째를 지정하여 원소를 삽입/삭제하는 연산을 구현해보았다면,

(2)에서는 특정원소의 바로 다음을 지정하여 원소를 삽입/삭제하는 연산을 정의하고 구현해 볼 것이다.

 

그러자면, 맨 앞에 원소를 추가 (삽입) 하거나 맨 앞의 원소를 제거 (삭제) 하는 연산을 지정하기가 애매해짐

이런 경우에도 동일한 방법을 적용하기 위해서, 이번에는 연결 리스트의 맨 앞에다가 데이터 원소를 담고 있지 않은, 그냥 자리만 차지하는 노드 -dummy node 리스트를 정의하자

0번째 노드에 dummy node를 정의하자..!

 

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

---

연산정의

1.길이 얻어내기
2.리스트순회
3.특정 원소 참조
4.원소삽입

insertAfter(prev, newNode)
: 노드를 주고 그 뒤에다가 삽입하기

	def insertAfter(self, prev, newNode):
		newNode.next = prev.next
		if prev.next is None:
			self.tail = newNode #맨끝에서 newNode삽입하는 경우에 tail을 옮겨주자
		prev.next = newNode
		self.nodeCount += 1
		return True

 

prev가 가리키는 node의 다음에 newNode를 삽입하고
성공/실패에 따라 True/False를 리턴

 

insertAfter(prev, newNode) -> 맨앞에 node는 어떻게 삭제할 것인가..
popAfter(prev) -> 맨 앞에서는 어떻게?

---> dummy node를 이용하자 0번째 node!

 

이미 구현한 insertAfter()를 호출하여 이용하는 것으로
(1) pos범위 조건확인
(2) pos == 1인경우에는 head뒤에 새 node 삽입
(3) pos == nodeCount + 1인 경우는 prev <- tail : 앞에서 찾아갈 필요없이 tail을 prev로 삼으면 됨
(4) 그렇지 않은 경우에는 prev <- getAt() : 앞에서 찾아감

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)

5.원소삭제

 

prev의 다음 node를 삭제하고 그 node의 data를 리턴

(1) prev가 마지막 node 일 때 prev.next == None
-> 삭제할 node없음
-> return None
(2) 리스트 맨끝의 node를 삭제할 때 curr.next = None
-> tail조정 필요
**연습문제 popAfter, popAt 구현하기

def popAfter(self, prev):

        #삭제할 다음 노드가 없을 경우
        if prev.next == None: 
            return None
        #일반적인 경우 삭제
        curr = prev.next
        prev.next = curr.next
        
        #맨 끝의 노드 삭제
        if curr.next == None:
            self.tail = prev
            prev.next = None
		self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        prev = self.getAt(pos-1)
        return self.popAfter(prev)

6.두 리스트 합치기
self.tail.next = L2.head.next
dummy node 제외하고 이어줌