추상적 자료구조 (Abstract Data Structures) : 내부 구현은 숨겨두고 밖에서 보이는것들 2가지 제공
1. Data
-ex 문자열 정수 레코드,,
2. A set of poerations
-ex 삽입 삭제 순회/ 정렬 탐색
기본적 연결 리스트
맨 앞 노드 Head 맨 끝 노드 Tail
앞에 있는것이 뒤에 있는것을 가르키도록 늘어놓은 것을 연결리스트 라고 한다.
각각의 아이템들은 노드라고 한다
노드 안에는 데이터와 링크가 들어있다, 노드 내 데이터는 다른 구조로 이루어질 수 있음 ex) 문자열/레코드/다른 연결리스트
리스트 앞 노드를Head 맨 끝 노드를 Tail 끝을 알고 있으면 데이터 삽입할때 편리하다
연결리스트의 추상적 자료구조 만들기 위해서는
1. node >> Date / Link 만들어 줘야함
2. LinkedList >> nodeCount / head / tail
이 두가지를 이용하여 LinkedList의 속성을 가지도록 만들어줄 수 있다.
보통 노드는 1부터 시작한다.
# pos번째 노드 찾기 메소드
def getAt(self, pos):
if pos <= 0 or pos > self.nodeCount: # post 가 0보다 작거나 노드 갯수보다 크면
return None # 널 리턴
i = 1 # 아니면 i 를 1로 지정
curr = self.head # curr 를 연결리스트 첫번째 노드 가르침
while i < pos: # i 를 증가 시키면서
curr = curr.next # curr 를 증가하면서
i += 1 # i 도 늘리고
return curr # 마지막 curr 리턴
배열 (O(1)) 연결리스트 O(N)
-------------------------------------------------------------------------
저장공간 연속한 위치 임이의 위치
특정 원소 지칭 간편 선형탐색과 유사
1. LinkedList 끝까지 선회하는 코드 tㅈㄷ
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
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):
if not self.head:
return []
List = []
curr = self.head
while curr is not None:
List.append(curr.data)
curr = curr.next
return List
def solution(x):
return 02. insert
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 )
prev = self.getAt(pos - 1) # 끼워 넣을 직전 노드 알아냄
newNode.next = prev.next # 삽입 노드 넥스트는 원래의 넥스트로함
prev.next = newNode # 원래 노드의 넥스트는 새로운노드를 가르킴
if pos == self.nodeCount + 1: # 맨뒤
self.tail = newNode # tail 을 새로운노드로 가르킴
self.nodeCount += 1
# 맨 뒤 삽입
return True시간 복잡도 : 맨 앞 O(1) 중간 O(N) 맨 끝 O(1)
3.delete
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
if pos == 1: # 1번 노드일때
curr = self.head
self.head = curr.next
if self.nodeCount == 1: # 노드 길이가 1일때
self.tail = self.head
else: # 2번 노드부터 맨 마지막까지
prev = self.getAt(pos-1)
curr = prev.next
prev.next = curr.next
if pos == self.nodeCount: #맨 마지막일때
self.tail = prev
self.nodeCount -= 1
return curr.data
4. 합치기
concat() 사용
ex)
L1.concat(L2)
def concat(self,L):
self.tail.next = L.head
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount삽입과 삭제를 할때마다 매번 맨 앞 부터 찾아가야하는 문제
해결 >>> 그 위치를 노드로 주고 삭제 및 삽입
맨 앞( index = 1 )에 일때는 문제가 된다.
>> 맨 앞에 dummy node 를 추가한 형태로 한다 (index = 0)
5.insertAfter(prev, newNode)
def insertAfter(self, prev, newNode):
newNode.next = prev.next
if prev.next is None: # tail 의 뒤에 새로운 노드를 삽입하는 경우
self.tail = newNode
prev.next = newNode
self.nodeCount += 1
return True6.insertAt(self, pos, newNode):
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
if pos != 1 and pos == self.nodeCount + 1: # 포스가 1이면 빈 리스트에 노드를 삽입하는 경우다,
prev = self.tail
else:
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
7.popAfter(prev)
def popAfter(self, prev):
# prev가 맨 마지막 노드인 경우를
curr = prev.next
answer = curr.data
# 삭제하는 노드가 맨 마지막 노드인 경우
if curr.next == None:
self.tail = prev
prev.next = None
else:
prev.next = curr.next
self.nodeCount -= 1
curr = None
return answer8.popAt()
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
else:
return self.popAfter(self.getAt(pos-1))
댓글