연결리스트는 말 그대로 연결된 리스트이다.
리스트(배열)자료구조에서 각 원소들이 호텔의 방에 하나씩 들어가 있었다면,
연결리스트에서 그 방들은 호텔에 갇힌것이 아닌, 독립적인 캠핑카가 된다.
그리고 서로의 꽁무늬에 'link'라는 연결고리를 달고 다니는데, 이 꼬리엔 아무것도 오지 않을 수도, 혹은 또 다른 캠핑카 한 대가 연결되어 기차같은 모양을 이룰수도 있다.
[자료 구조 정의]
1. Node (캠핑카)
class Node:
def __init__(self,item):
self.data = item #캠핑카에 탑승한 운전자
self.next = None #꽁무늬 (link 가 여기선 next) 초기화
item, next 는 각자 캠핑카에 탑승한 자료, 캠핑카의 뒤에 붙은 꽁무늬와 같다.
노드를 초기화해줄 땐 어떤 자료가 들어갈지, 반드시 언급해줘야 하므로 (그래야 존재 가치가 있다고 해야하나)
item을 사용하여 Node를 초기화해주었다.
2. Linked List (캠핑카 묶음 정보)
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = None
self.tail = None
캠핑카들이 서로 꼬리에 꼬리를 물고 얽혀있을 때, 이 캠핑카들을 종합적으로 관리할 장부가 필요한데, 이것이 바로
Linked List라고 할 수 있다.
총 몇 대의 캠핑카들이 얽혀있는지 (nodeCount - 캠핑카들을 순회할 때 필요), 어떤 캠핑카가 맨 앞에 있는지 (head - 그래야 캠핑카가 어디있는지 찾을 수 있으니까), 어떤 캠핑카가 맨 뒤에 있는지(tail - 맨 끝에 새 캠핑카를 추가하거나 수정 할때 등..필요) 등을 적어서 관리해준다.
[연산 정의]
1. 특정 원소 참조하기
def getAt(self,pos): #self 는 linked list, pos는 알고 싶은 index
if pos<1 or pos>self.nodeCount: #범위에 맞지 않는 index일 경우
return None
i=1 #1번 index부터 시작
curr = self.head #curr-현재 순회 노드
while i<pos:
curr = curr.next
i+=1
#i==pos
return curr
주석으로 설명했듯, pos 번째 순서에 있는 node를 반환하는 파이썬 코드이다.
pos가 범위 이외의 index를 찾는 경우를 다루는 첫번째 if문에 이어, 1번 노드부터 탐색을 시작한다. 현재 순회중인 노드를 curr에 저장하고, curr.next로 curr의 다음 노드로 이어지며 while문을 돌다가, i가 pos와 같아지는 순간 while문을 탈출한다. 그렇게 pos번째 node인 curr을 반환하게 된다.
배열에선 특정 인덱스의 원소를 가져오고자 할 때, list[index]와 같이 한번에 그 자리에서 찾아올 수 있지만 (O(1)), 연결리스트는 메모리 속에 배열 처럼 연속하여 존재하지 않고 임의의 공간에 흩어져 존재하기 때문에 서로간 연결된 꼬리로 하나하나 찾아가야 한다. 그렇기에 시간 복잡도는 O(n)이 된다.
2. 리스트 순회
def traverse(self):
answer = [] #node의 item 차례로 저장
curr = self.head
for i in range(self.nodeCount):
answer.append(curr.data)
curr = curr.next #curr을 바꿔가며 순회
return answer
linked list에 저장된 노드들의 data 값들을 하나하나 저장하는 순회코드이다. 각 노드들의 item 값은 answer에 차례로 append되어 저장된다.
바로 위의 getAt 함수를 써서, 1에서부터 nodeCount까지 참조하여 추가하는 식으로도 순회할 수 있겠지만, 그렇게 된다면 이미 순회하여 원하는 data를 얻어낸 노드를 계속해서 또 거쳐가야할 것이므로, 리스트를 한바퀴 돌면서 바로바로 data를 저장하는 형식으로 순회한다.
3. 원소 삽입
리스트의 중간(pos번째)에 원소를 삽입하는 기본 순서는 다음과 같다
1. 새 노드의 link에 pos번째 노드(뒤로 밀릴 노드) 연결
2. pos-1번째 노드의 link에 새 노드 연결
3. nodeCount (전체 노드 수) 1 증가
먄약 pos-1 번째 노드의 link를 새 노드에 연결하는 작업 (2번)을 제일 먼저 하게 된다면, pos 번째에 있던 노드(뒤로 밀릴 노드)를 원랜 pos-1번째 노드의 link로 이어서 찾았었는데 이것이 먼저 끊기게 된 셈이므로, 아예 찾을 수 없게 되어 새 노드의 link로 이어 붙일수도 없게 된다.
그러므로, 기존 pos-1~ pos번째 노드 사이의 연결은 우선 유지해 주고 새 노드를 잇기 시작해야 한다.
이것을 코드로 나타내면 다음 함수로 나타낼 수 있다.
def insertAt(self, pos, newNode): #pos 위치에 newNode 삽입
if pos<1 or pos>self.nodeCount+1:#수가 하나 늘어남에 유의
return False
if pos == 1: #맨 앞에삽입
newNode.next = self.head
self.head = newNode
else: #앞 노드의 next - newNode - 뒤 노드 연결
if pos == self.nodeCount+1:
prev = self.tail #tail 이용하여 맨 뒤 노드 찾기
else:
prev = self.getAt(pos-1) #앞 노드
newNode.next = prev.next #new Node와 그 다음노드 연결 (맨 끝 노드일 경우 NULL에 연결)
prev.next = newNode #newNode와 그 앞 노드 연결
if pos == self.nodeCount+1: #맨 뒤에 삽입 -> 앞 노드와 이어진 상태.
self.tail = newNode
self.nodeCount+=1 #노드 수 증가
return True
빈 리스트일 경우, 두 번째 if 문과 그 다음 if문에 의해 삽입된 노드는 head이자 tail이 된다.
원소 삽입 연산의 복잡도
맨 앞에 삽입하는 경우: O(1) //head 바로 찾아서 이용
중간에 삽입하는 경우: O(n) // 앞, 뒤 상관 없이 리스트 크기가 커지면 커짐
맨 끝에 삽입하는 경우: O(1) //tail 바로 찾아서 이용
4. 원소 삭제
특정 위치(pos)번째의 노드를 삭제하고 그 값을 반환하는 알고리즘의 순서는 다음과 같다.
1. pos번째 노드를 찾고 그 data값을 저장한다.
2. pos-1번째의 노드(맨 앞일 경우 head)의 링크를 pos번째의 노드의 링크가 가리키는 곳을 가리키도록 한다.
3. 전체 노드의 수 1 감소
def popAt(self, pos):
#pos의 범위 확인 -> 빈 리스트도 처리
if pos<1 or pos>self.nodeCount:
raise IndexError
else:
#맨 앞
if pos==1:
answer = self.head.data
self.head = self.head.next
#꼬리도 같이 해줘야 할 경우
if self.nodeCount==1:
self.tail = None
#2개 이상
else:
prev = self.getAt(pos-1)
curr = prev.next
answer = curr.data
prev.next = curr.next
if pos==self.nodeCount:
self.tail = prev
self.nodeCount-=1
return answer이 때, 앞 노드를 찾을 수 없는 경우, 즉 noceCount가 1인 유일한 노드인 경우, head를 삭제하는 경우는 따로 처리해주었다.
원소 삭제 연산의 복잡도
맨 앞을 삭제하는 경우: O(1) //head 바로 찾아서 이용
중간을 삭제하는 경우: O(n) // 앞, 뒤 상관 없이 리스트 크기가 커지면 커짐
맨 끝을 삭제는 경우: O(n) //tail 바로 찾아서 이용할수 없음 - 앞 노드가 필요하므로 일일이 순회해야 함.
5. 두 리스트 연결
def concat(self,L):
self.tail.next = L.head
if L.tail:
self.tail = L.tail
self.nodeCount +=L.nodeCount
연결리스트의 끝에 새로운 연결리스트(L)을 추가하여 이어붙이는 연산이다.
L이 비어있다면 tail이 null이 아니라, 그대로 self.tail이어야 하므로 이에대한 처리도 잊지 않고 해준다.
[Dummy Node]
어떤 노드(prev)의 바로 뒤에 노드를 추가하거나 삭제하려고 할 때, 만약 삭제/삽입하려는 위치가 리스트의 맨 앞이라면 따로 처리를 해주는 과정 (if문 이용)을 거쳤다. 이런 번거로운 과정을 피하기 위해, head에 dummy node라는, 내용은 비어있지만 노드 역할을 하는 노드를 만들게 된다. 이때 dummy node의 인덱스는 0이다.(값이 있는 노드들은 인덱스가 1부터 시작하도록 짜왔음)
class LinkedList: #DummyNode를 추가하여 연결리스트 초기화
def __init__(self):
self.nodeCount = 0
self.head = Node(None) #Dummy Node
self.tail = None
self.head.next = self.tail #결론은 아무것도 없는 빈 연결리스트
연결리스트를 초기화할 때 Dummy Node에 관한 선언, 초기화도 같이 수행하고 있다.
1. 리스트 순회
def traverse(self):
result = []
curr = self.head #Dummy Node
while curr.next:
curr = curr.next #Dummy Node 다음부터 시작
result.append(curr.data)
return result
Dummy Node가 추가됐을 때의 순회문이다. curr 이 head에서 바로 시작하지 않고, curr.next 부터 시작하여 Dummy Node 이후부터 순회하게 된다.
2. 특정 원소 참조하기
def getAt(self,pos): #self 는 linked list, pos는 알고 싶은 index
if pos<0 or pos>self.nodeCount: #범위에 맞지 않는 index일 경우
return None
i=0 #0번 index (Dummy Node)부터 시작
curr = self.head #curr-현재 순회 노드
while i<pos:
curr = curr.next
i+=1
return curr
Dummy Node가 없을 때와 달리 i가 0번부터 시작하며, pos가 0으로 주어졌을 때도 head를 리턴하면 되므로 pos 에 관한 예외 검사는 1이 아닌 0으로 수행한다.
3. 원소 삽입하기
1) 매개변수가 앞 노드 일때
#삽입 성공시 True 리턴
def insertAfter(self,prev, newNode): #prev는 앞노드
newNode.next = prev.next
#tail이 변화가 있을 경우
##head는 항상 DummyNode이므로 신경X
if prev.next is None:
self.tail = NewNode #최초로 삽입된 노드에만 적용
prev.next = NewNode
self.nodeCount+=1
return True
주어진 노드 prev 뒤에 새 노드를 삽입하고 성공시 True를 리턴하는 함수. tail의 변화가 있을 때만 처리하고 head는 항상 Dummy Node이므로 따로 변경해주지 않아도 된다.
2)매개변수가 인덱스일때
1)에서 구현한 함수를 호출하여 인덱스가 주어졌을 때 해당 인덱스에 노드를 삽입하는 함수를 만들어보자.
def insertAt(self,pos,newNode):
#prev를 찾을 수 없음 1 - out of range
if pos<1 or pos>self.nodeCount+1:
return False
else: #정상범위
#prev 찾기
if pos!=1 and pos == self.nodeCount+1:#prev가 tail인 경우 바로 찾기,pos가 1인경우는 tail이 없음에 유의
prev = self.tail
else:
prev = getAt(pos-1) #head일 경우 포함
return insertAfter(prev,newNode)
getAt을 이용해 prev를 불러온 후, insertAfter로 바로 삽입해 주었다. 맨 뒤에 삽입될때 prev를 tail로 바로 불러와서 처리한다. 0번에도 노드가 존재해 맨 앞에 삽입할 때와 그렇지 않을 때를 구분할 필요가 없어졌다.
4. 원소 삭제하기
prev 노드를 이용해 바로 다음 노드를 삭제하는 함수이다. 이 때 prev 자체가 아닌 그 이후의 노드를 삭제하는 것이므로, 인자로 넘겨받은 prev이후가 null일 경우, 즉 prev가 tail인 경우도 고려해야 한다. 이 땐 None을 return한다.
혹은 prev가 끝에서 두번째 노드일 경우, 맨 마지막 노드가 삭제되는 것이므로 tail을 조정해야 한다. 맨 앞 노드를 삭제하는 경우는 dummy node가 존재하므로 앞선 원소 삭제 함수와 달리 따로 유의하지 않아도 된다.
def popAfter(self, prev):
#prev 노드 이후의 노드 삭제, 데이터 리턴.
#삭제할수 없는 경우 - prev가 마지막 노드 or 빈리스트
if prev.next == None:
return None
else:
curr = prev.next #삭제될 거
ans = curr.data
prev.next = curr.next
#tail이 삭제됐다면 update
if curr.next == None:
self.tail =prev
self.nodeCount-=1 #노드개수 업데이트
return ans
def popAt(self, pos):
#pos번째를 삭제함
#pos의 범위 확인
if pos<1 or pos >self.nodeCount:
raise IndexError
else:
prev = self.getAt(pos-1)
return self.popAfter(prev)
popAt()에 삭제하고자 하는 인덱스를 넘겨주면, prev를 찾고 그것을 이용하여 해당 노드를 삭제, 저장되있던 데이터 값을 리턴한다.
5. 두 리스트 연결
def concat(self,L):
self.tail.next = L.head.next
if L.tail: #원소가 하나라도 존재함 -> tail이 null이 아니므로 이 것을 가져와야 함
self.tail = L.tail
self.nodeCount+=L.nodeCount
만약 자신과 L을 연결할 때, 자신의 tail에 L의 head를 바로 붙이던 저번(dummy node가 없을 때)과 달리, L의 head의 next를 연결해주어야 한다. 또한, tail과 node 갯수 업데이트도 잊지 않고 해주어야 한다.
'컴맹탈출기 > Data Structure' 카테고리의 다른 글
| 이진 탐색 트리 (Binary Search Trees) (0) | 2020.12.02 |
|---|---|
| 큐 (Queue) in Python (0) | 2020.12.01 |
| 후위 표기법 (Postfix Notation) (0) | 2020.12.01 |
| 양방향 연결리스트 (Doubly Linked List) in Python (0) | 2020.12.01 |
| 스택(Stack) in Python (0) | 2020.12.01 |