리스트 연산
삭제
연결
이제 이거 두개가 남았다.
삭제는 삽입과 비슷하지만 다르다!
prev의 next를 현재 노드의 뒷 노드로 지정해주고
전체 count를 -1해주면 된다.
하지만 언제나 예외가 우릴 괴롭힌다.
예외의 경우는 맨 뒤와 맨 앞의 내용을 삭제할 때이다.
맨 앞은 prev가 없으므로 두번째 노드를 head로 지정해주면 된다.
하지만 맨 뒤는 지정해줄 수가 없어서 중간값과 마찬가지로 맨 앞에서부터 맨 뒤까지 순회해야한다..
연결을 할때는 앞리스트.concat(뒷 리스트) 해주고
tail을 바꿔준다.
def concat(self,L):
self.tail.next = L.head
self.tail = L.tail
self.nodeCount += L.nodeCount이러면 맨 뒷 노드의 다음 노드가 다음 리스트의 헤드가 된다.
그리고 다음 리스트의 tail이 전체의 tail이 되고
리스트의 길이도 더해준다.
하지만 여기서 주의해야 할 점은
뒤에 이어질 것이 없다면 tail이 없는 것을 조심해야 한다.
따라서
def concat(self,L):
self.tail.next = L.head
if L.tail: #L.tail이 유효한 경우만!
self.tail = L.tail
self.nodeCount += L.nodeCount삽입과 삭제, 병합이 쉬운것이 연결리스트의 장점이다.
연결리스트 삭제 코드를 짜보았다.
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount + 1:
raise IndexError
if pos == 1:
n= self.head
self.head = n.next
if self.nodeCount == 1:
self.head = None
self.tail = None
else:
prev = self.getAt(pos-1)
n = prev.next
prev.next = n.next
if pos == self.nodeCount:
n = self.tail
self.tail = self.getAt(pos-1)
self.nodeCount -= 1
return n
코드를 이렇게 짰더니 예시 코드만 실행이 되고
채점하니 틀렸다고 나왔다.
그래서 다른 답들을 찾아보았다.
ㅎ.. 맨 첨에 nodeCount+1로 돼어있었다
정말 어이없는데서 실수를 했다.
이런 데서 실수 하는 경우가 많을 것 같으니
앞으로는
글로 조건 쓰기 -> 코드로 구현
이런식으로 방법을 바꿔봐야겠다
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount :
raise IndexError
if pos == 1:
n= self.head
self.head = n.next
if self.nodeCount == 1:
self.head = None
self.tail = None
else:
prev = self.getAt(pos-1)
n = prev.next
prev.next = n.next
if pos == self.nodeCount:
n = self.tail
self.tail = self.getAt(pos-1)
self.nodeCount -= 1
return n.data
그리고 마지막에 꼭 n.data로 써주어야 한다.
그리고 중간에 if 문을 혹시나 해서 else안으로 넣어주었더니 잘 작동한다.
n.data로 써주어야 하는 이유는 아마 그 안의 데이터 값이랑 뭔가 다른것같다.
지금은 맨 마지막 값을 삭제하기 위해선 처음부터 끝까지 훑어보고 와야 했다
하지만 이제 이 삽입 삭제가 유연한 연결리스트를 효율적으로 사용할 수 있도록 새로운 메서드들을 만들 것이다.
insertAfter(prev,newNode) : prev가 가리키는 node의 다음에 newNode를 삽입하고 성공/실패에 따라 True False를 리턴
-> 그럼 맨 앞에서는 어떻게 하는데? =>맨 앞의 prev를 만들어주자
popAfter(prev) : 그 위치 앞에것을 삭제하라
-> 그럼 맨 앞에서는 어떻게..? =>맨 앞의 prev를 만들어주자
=> 더미 노드를 만들어주자!
그래서 이제 linkedlist에 더미노드를 추가해줘서
'0'번을 만들어준다.
class LinkedList:
def__init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail=None
self.head.next = self.tail
이런식으로 더미노드가 생기게 된다.
그래서 traverse는 아주 약간 바뀌게 되는데, curr 이 none이면 while문이 멈추는게 아니고, curr.next가 none이면 while문이 멈추도록 설계된다
(curr이 none일 때 멈추면 더미노드에서 멈추기 때문,,)
getAt도 조금 바뀌게 된다.
i가 1부터 시작하는게 아닌 0부터 시작하게 된다.
또 pos가 원래는 <1일때 none을 리턴했는데, 이제 <0 일때 none을 리턴하도록 바뀐다.
insertAfter(self, prev, newNode) : newNode.next = prev.next prev.next = newNode self.nodeCount +=1 return True
문제가 되는건 tail의 뒤에 노드를 삽입 할 때이다!
if prev.next is None : self.tail = newNode
이 코드를 추가해서 tail을 뉴 노드로 바꿔준다.
그럼 더미노드가 있을 때 insertAt()은 어떻게 바뀔까?
def insertAt(self,pos,newNode): if pos<1 or pos>self.nodeCount+1: return False #pos의 prev를 결정해준다. #pos가 1이면서 nodeCount도 1이면 더미노드만 있는 빈 리스트에 넣는 것이므로 if pos != 1 and pos == self.nodeCount +1 : prev = self.tail else: prev = self.getAt(pos-1) #prev 뒤에 값을 넣어준다 return self.insertAfter(prev,newNode)
비슷하겍 prev의 다음 노드를 삭제하고
curr의 next가 prev의 next가 된다.
prev가 마지막 node일 때 none을 리턴하자!
리스트의 맨 끝 노드를 삭제할 때는 tail조정을 잘 해주자!
(얘네는 연습문제로 만들어 볼 것)
def popAfter(self, prev):
if prev.next == None : return None
curr = prev.next
if curr.next == None : self.tail = prev
prev.next = curr.next
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
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)이번엔 한번에 성공했다!!
연결은
더미가 있을 때 두 리스트의 연결은 두번째 리스트의 head.next를 처음 리스트의 tail.next로 지정해준다!
원래 리스트의 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
양방향 연결 리스트(doubly linked lists)
next만 있다가,prev를 이용할 수 있는 리스트가 양방향 연결 리스트가 된다!
node의 구조를 확장할 필요가 있다.(나는 첨부터 왜 이전으로 가는건 안만든거지?하고 생각했는데 그냥 나중에 차근차근 배우는거였다..)
더미노드도 처음과 끝에 모두 두게 된다!!
어휴 이제 속시원하네
class Node:
definit(self,item):
self.data=item
self.prev = None
self.next = None
첨부터 이렇게 했으면 좋겠다고 생각했다..
근데 이게 양방향 연결 리스트였다니~ㅋㅋ
class DoublyLinkedList :
def init (self,item):
self.nodeCount = 0
self.head =Node(None)
self.tail =Node(None)
self.head.prev = None
self.head.next=self.tail
self.tail.prev = self.head
self.tail.next = None
다른 코드들은 한번에 쓰겠다..
class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = Node(None)
self.head.prev = None
self.head.next = self.tail
self.tail.prev = self.head
self.tail.next = None
def __repr__(self):
if self.nodeCount == 0:
return 'LinkedList: empty'
s = ''
curr = self.head
while curr.next.next:
curr = curr.next
s += repr(curr.data)
if curr.next.next is not None:
s += ' -> '
return s
def getLength(self):
return self.nodeCount
def traverse(self):
result = []
curr = self.head
while curr.next.next:
curr = curr.next
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
if pos > self.nodeCount // 2:
i = 0
curr = self.tail
while i < self.nodeCount - pos + 1:
curr = curr.prev
i += 1
else:
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertAfter(self, prev, newNode):
next = prev.next
newNode.prev = prev
newNode.next = next
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
더미가 두개 생겨서 리스트가 역순회 할때는
이렇게 prev를 두번 했을때 아무것도 없을 때 멈춰야 한다.
def reverse(self):
result=[]
curr=self.tail
while curr.prev.prev:
curr=curr.prev
result.append(curr.data)
return result
원소를 삽입하거나 삭제할 떄 가장 좋은점이 있다..
헤드랑 테일을 조정하지 않아도 된다는 것!!!
그게 나의 실수를 막 유발하는 요인이였는데
이로인해 실수가 줄것같은 느낌~
새로운 노드의 뒷 노드를 next라고 정해주고 여기에는 Prev.next를 넣어준다.
새로운 노드의 앞뒤를 정해주고, 이전노드와 이후노드의 사이를 newNode라고 정해주는 딱 4줄이 핵심!
그리고 카운트를 하나 더해주면 끝
(코드는 위에 나와있다)
특정 원소를 얻어낼 때는 한쪽방향으로만 하는것과 완전히 동일
만약 insertAt을 한방향과동일하게 쓰는데
prev를 여전히 getAt()으로 쓰기 때문에 비효율적
이제 getAt메소드를 수정해보자!!
이진탐색으로 수정!!(코드는 위에 나와있다)
절반보다 오른쪽에 있으면 테일부터 찾아가고
절반보다 왼쪽에 있으면 헤드부터 찾아나가는 방식으로 getAt을 바꾼다. 여전히 선형 알고리즘임은 변함이 없다.
(근데 만약에 동일한 값이 있으면 어떡함???)
이번 강의를 배우면서
문제를 풀 때
예외가 많이 없는 자료구조를 만드는게
좋은것 같다는 생각이 들었다
