연결 리스트
def insertAt(self, pos, newNode) :
pos가 가리키는 위치에 ( 1<= pos<= nodeCount +1)
newNode 를 삽입하고 성공/실패에 따라 True/False를 리턴
L.insertAt(pos, newNode)
pos-1 => prev
pos => prev.next ==> prev.next <-newNode
nodeCount += 1
def insertAt(self, pos, newNode) :
prev = self.getAt(pos -1)
newNode.next = prev.next
prev.next = newNode
====> 순서 중요!!!
self.nodeCount += 1(1) 삽입하려는 위치는 리스트 맨 앞일때
=> prev 없음
=> Head 조정 필요
(2) 삽입하려는 위치가 리스트 맨 끝일 때
=> Tail 조정 필요
(3) 빈 리스트에 삽입할 때?
=> 이 두조건에 의해 처리됨
def insertAt(self, pos, newNode) :
if pos < 1 or pos>self.nodeCount + 1:
return False
if pos = 1 :
newNode.next = self.head
self.head = newNode
else :
prev = self.getAt(pos -1)
newNode.next = prev.next
prev.next = newNode
if pos == self.nodeCount + 1:
self.tail = newNode
self.nodeCount += 1
return True (4) 삽입하려는 위치가 리스트 맨 끝일 때, 즉 post == nodeCount + 1인 경우?
prev == tail
tail.next = newNode
==> 맨 앞에서부터 찾아갈 필요 없이 한번에 넣을 수 있다.
else :
if pos == self.nodeCount + 1:
prev = self.tail
else :
prev = self.getAt(pos-1)
newNode.next = prev.next
prev.next = newNode(5) 연결 리스트 원소 삽입의 복잡도
- 맨 앞에 삽입하는 경우 : O(1)
- 중간에 삽입하는 경우 : O(n)
- 맨 끝에 삽입하는 경우 : O(1)
연결리스트 연산 - 원소의 삭제
def popAt(self,pos) :pos가 가리키는 위치의 (1<=pos<=nodeCount) node를 삭제하고
그 node의 데이터를 리턴
==> prev.next <-curr.next , curr 출력, nodeCount-1
(1) 삭제하려는 node가 맨 앞의 것일때
-> prev없음
-> Head 조정 필요
(2) 리스트 맨 끝의 node를 삭제할 때
-> Tail
(3) 유일한 노드를 삭제할떄?
=> 이 두 조건에 의해 처리되는가?
(4) 삭제하려는 node가 마지막 node일 때, 즉 pos == nodeCount인 경우? 한 번에 처리할 수 없다. (prev를 찾을 방법이 없으므로)==> 앞에서부터 찾아와야한다.
(5) 연결리스트 원소 삭제의 복잡도
- 맨 앞에서 삭제하는 경우 : O(1)
- 중간에서 삭제하는 경우 : O(n)
- 맨 끝에서 삭제하는 경우 : O(n)
연결리스트 연산 - 두 리스트의 연결
def concat(self, L) :
self.tail.next = L.head
self.tail = L.tail
self.nodeCount += L.nodeCount- 만약 빈 리스트를 연결하게 된다면
if L.tail:
self.tail = L.tail
연습문제
def popAt(self, pos):
data = 0
if pos < 0 or pos > self.nodeCount:
raise IndexError
if self.nodeCount == 1:
data = self.head.data
self.head = None
self.tail = None
else:
## pos == 1은 pos가 head를 가리킬때
if pos == 1:
data = self.head.data
self.head = self.head.next
else:
prev = self.getAt(pos - 1)
## post == self.nodeCount는 pos가 tail.을 가리킬때
if pos == self.nodeCount:
data = prev.next.data
prev.next = None
self.tail = prev
else:
data = prev.next.data
prev.next = prev.next.next
self.nodeCount -= 1
return data삭제하는 data값을 출력
