7강
데이터 + 링크로 합쳐진 추상적 자료 구조다. 데이터는 값을 가지는 부분이고 링크는 다음 노드를 가리키는 주소이다. 크게보면 노드 -> 노드 -> 노드 ->....->노드 구조라고 생각하면 쉬울듯 하다.
내용
노드의 구조
노드는 데이터와 링크로 이루어져 있다.
class Node:
def __init__(self, item):
self.data = item
self.next = None연결리스트의 구조
연결리스트는 첫 노드를 가리키는 head, 마지막 노드를 가리키는 tail그리고 노드의 수를 저장하는 nodeCount로 만들었다.
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = None
self.tail = None노드 탐색
특정 원소를 참조
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount: #크기를 벗어난 위치
return None
i = 1
curr = self.head #제일 앞부터
while i < pos: #해당 위치까지
curr = curr.next #한칸씩 앞으로
i += 1
return curr문제
연결리스트를 순환하는 함수
def traverse(self):
answer = []
i = 1 #처음부터
while i <= self.nodeCount: #마지막 까지
answer.append(self.getAt(i).data) #데이터 저장
i += 1
return answer;GitHub
8강
노드와 연결리스트의 구조, 탐색과 순환에 대해 알아보았다면 연결 리스트 내에 노드 삽입, 삭제에 대한 강의 였다.
내용
삽입
원소를 삽입하기 위해선 3가지 단계를 거쳐야한다.
1번.새로운 노드의 링크가 이전 노드의 링크가 가리키던 노드를 가리켜야한다.
2번.이전 노드의 링크가 새로운 노드를 가리켜야한다.
3번.노드의 수 1증가
특히 주의를 해야할건 1번과 2번의 순서는 반드시 지켜져야 한다. 변수에는 한번에 하나의 값만 저장될 수 있기 때문에 이전노드가 다음노드의 주소를 잃는 순간 다시 찾을 수 없다. 따라서 새로운 노드의 링크부터 저장되어야 한다.
또한 맨앞에 삽입 할때, 맨뒤에 삽입 할때는 살짝 다른 처리과정이 필요하다.
맨앞 : 이전노드x, head 조정
맨뒤 : tail을 이용해서 삽입, tail조정
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 #head 조정
else: #맨앞 x
if pos == self.nodeCount + 1: #맨 뒤 삽입
prev = self.tail #tail 이용해서 한번에 이전노드로 이동
else: #중간
prev = self.getAt(pos - 1) #이전 노드
newNode.next = prev.next #이전 노드의 다음 노드 링크
prev.next = newNode #이전 노드는 새로운 노드 링크
if pos == self.nodeCount + 1: #맨 뒤 삽입
self.tail = newNode #tail 조정
self.nodeCount += 1 #갯수 +1
return True삭제
원소를 삭제하기 위해서도 3단계가 필요하다.
1번.이전노드의 링크가 삭제할 노드의 링크가 가리키는 노드를 가리킴
2번.삭제할 노드의 데이터를 꺼냄
3번.노드 수 -1
삭제 또한 마찬가지로 맨 마지막과 맨앞은 살짝 다른 처리과정이 필요하다.
맨앞: 이전 노드x, head 조정
맨뒤: 삽입과 다르게 tail활용x, tail 조정
노드가 1개: head조정, tail조정
연결
두개의 노드를 이어붙히는 과정은 비교적 간단히 구현할 수 있다.
def concat(self, L):
self.tail.next = L.head #마지막 노드가 다른 링크의 맨 앞를 가리킴
if L.tail: #다른 링크가 빈 노드가 아니면
self.tail = L.tail #tail은 다른 링크의 마지막 링크를 가리킴
self.nodeCount += L.nodeCount #노드의 수 추가문제
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount: # 범위 벗어남
raise IndexError
curr = None #삭제할 노드를 저장
if pos == 1: #맨앞
curr = self.head
if self.head == self.tail: #노드가 1개인가?
self.head = None
self.tail = None
else: #노드가 2개 이상
self.head = curr.next
else: #맨앞이 아님
prev = self.getAt(pos-1)
curr = self.getAt(pos)
if pos == self.nodeCount: #맨뒤 인가?
self.tail = prev #tail 수정
prev.next = curr.next #next 수정
self.nodeCount -= 1 #갯수 수정
return curr.dataGitHub
9강
이전의 연결 리스트를 확장하여 더욱더 편리하게 연결 리스트를 구현해보자
내용
이전 노드를 전달받아 순회, 탐색, 삽입, 삭제를 처리하지만 맨앞에 dummy node를 두어 쉽게 처리 한다.
새로운 연결리스트 구조
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None) #dummy node
self.tail = None
self.head.next = self.tail순회
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: #더미도 고려해야하기 때문에 0포함
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 popAfter(self, prev):
if prev.next == None: # prev가 마지막
return None
curr = prev.next
if curr.next == None: #마지막 노드
prev.next = None
self.tail = prev
else: #마지막 노드가 아닐때
prev.next = curr.next
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)GitHub
