추상적 자료구조(abstract data structures)
data
예:정수, 문자열, 레코드,...
a set of operations
삽입, 삭제, 순회, ...
정렬, 탐색,...
기본적 연결 리스트
앞에있는것이 뒤에있는것을 가르키도록, 각각의 아이템을 node
node내의 데이터는 다른 구조로 이루어질 수 있음
예: 문자열, 레코드, 또 다른 연결 리스트 등
리스트의 맨 앞을 가르킬때 -> head
리스트의 맨 끝 노드 -> tail
연결 리스트 안에 몇개 있는지 기록
노드 안에는 data, 다음 node를 가지고있음
class Node:
def __init__(self, item):
self.data = item
self.next = None
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = None
self.tail = None즉, 노드의 개수는 0, head, tail 아무것도 가르키고있지않은
비어있는 연결 리스트
연산 정의
- 특정 원소 참고(k번째)
- 리스트 순회
- 길이 얻어내기
- 원소 삽입
- 원소 삭제
- 두 리스트 합치기
특정 원소 참조
0 다른 목적에 이용하기 위해 1부터 사용
k번째 원소를 찾아라.
def getAt(selt, pos): //
if pos <= 0 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while < pos:
curr = curr.next
i += 1- 원소 삽입
- 원소 삭제
- 두 리스트 합치기
연결 리스트 연산 - 원소의 삽입
def insertAt(self, pos, newNode):
pos가 가리키는 위치에 (1<=post <= nodeCount + 1)
newNode를 삽입하고
성공/실패에 따라 True/False를 리턴
제일 먼저 할일은 prev 위치 찾기
def insertAt(self, pos, newNode):
prev = self.getAt(pos -1)
newNode.next = prev.next //new노드의 next를 prev에 가리키도록 하고,
prev.next = newNode //그다음에 연결
self.nodeCount += 1
코드 구현 주의사항
(1)삽입하려는 위치가 리스트 맨 앞일때
-> prev없음
-> 대신에 Head 조정 필요
(2) 리스트의 맨 끝일때
-> 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
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
그런데 잠깐, 삽입하려는 위치가 리스트 맨 끝일때,
즉 pos == nodeCount + 1 인 경우?
prev == 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
else:
if pos == self.nodeCount + 1:
prev = self.tail //끝으로 바로간다
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연결 리스트 원소 삽입의 복잡도
맨앞에 삽입하는경우 : O(1) //한번에 그냥 head를 찾기때문에
중간에 삽입하는 경우: O(n) //삽입되는 위치에 따라 앞쪽이냐,끝쪽이냐 달라지긴하지만, 일반적으로 리스트의 길이에 따라서 커지기때문에 그래서 linear연산
맨 끝에 삽입하는 경우 : O(1) //
연결 리스트 연산 - 원소의 삭제
def popAt(self, pos):
pos가 가리키는 위치의(1 <= pos <= nodeCount)
node를 삭제하고
그 node의 데이터를 리턴
코드 구현 주의사항
(1)삭제하려는 node가 맨 앞의 것일 때
-> prev없음 -> head 조정 필요
(2) 리스트 맨 끝의 node를 삭제할때
->tail 조정 필요
그런데 유일한 노드를 삭제할 때?-> 이 두 조건에 의해 처리되는가?
그런데 잠깐, 삭제하려는 node가 마지막 node일 때,
즉 pos == nodeCount인 경우?
하지만 한 번에 처리할 수 없다.
(prev를 찾을 방법이 없으므로) ->앞에서부터 찾아와야함
연결 리스트 원소 삭제의 복잡도
맨앞에 삭제하는경우 : O(1)
중간에 삭제하는 경우: O(n)
맨 끝에 삭제하는 경우 : O(n) // 리스트의 길이에 비례
연결 리스트 연산 - 두 리스트의 연결
def concat(self, L):
연결 리스트 self의 뒤에 또다른 연결 리스트인 L을 이어붙임
def concat(self,L):
self.tail.next = L.head
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount