- 추상적 자료구조(Abstract Data Structure)
- Data(정수, 문자열, 레코드...)
- A set of operations(삽입, 삭제, 조회, 정렬, 탐색...)
- 기본적 연결리스트
- 노드는 데이터와 링크로 이루어진다.
- 노드 내의 데이터는 다른 구조로 이루어질 수 있음
- 리스트의 맨 앞을 Head, 맨 뒤를 Tail이라고 한다.
- 노드가 몇개 있는지까지 기록해두면 편하다.
- 링크드 리스트 구현
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
연산 정의
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 <= 0 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = pos.next
i += 1
return curr
| |
배열 |
연결리스트 |
| 저장 공간 |
연속한 위치 |
임의의 위치 |
| 특정 원소 지칭 |
매우 간편 |
선형 탐색과 유사 |
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):
result = []
curr = self.head
while curr != None :
result.append(curr.data)
curr = curr.next
return result
- 원소의 삽입
- def insertAt(self, pos, newNode):
- pos가 가리키는 위치에 (1 <= pos <= nodeCount + 1)
- newNode 삽입
- 성공 실패에 따라 True/False를 리턴
- pos-1을 prev라 한다.
- newNode의 뒤쪽 링크를 pos로 지정
- prev가 newNode를 가리키도록 한다.
- nodeCount += 1을 한다.
- 주의 사항
- 삽입 하려는 위치가 리스트 맨 앞일 때(prev 없음, head 조정 필요)
- 삽입 하려는 위치가 리스트 맨 끝일 때(Tail 조정 필요)
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 <= 0 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = pos.next
i += 1
return curr
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)
- 중간: O(n)
- 맨 끝: O(1)
- 원소의 삭제
- pos가 가리키는 위치(1 <= pos <= nodeCount)
- node 삭제
- 그 node의 데이터 리턴
- pos-1을 prev로 한다.
- prev.next를 curr.next로 조정
- 삭제하려는 node가 맨 앞일때(prev없음 Head 조정 필요)
- 리스트 맨 끝 node 삭제할때(tail 조정 필요)
- 유일한 노드를 삭제할때
- 연결리스트 원소 삭제의 복잡도
- 맨앞: O(1), 중간: O(n), 맨 끝: O(n)
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 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
def popAt(self, pos):
answer = 0
if pos < 1 or pos > self.nodeCount:
raise IndexError
if self.nodeCount == 1:
curr = self.head
answer = curr.data
self.head = None
self.tail = None
self.nodeCount = 0
else:
if pos == 1:
curr = self.head
answer = curr.data
self.head = curr.next
else:
prev = self.getAt(pos-1)
curr = prev.next
answer = curr.data
if pos == self.nodeCount:
self.tail = prev
prev.next = None
else:
prev.next = curr.next
self.nodeCount -=1
curr = None
return answer
def traverse(self):
result = []
curr = self.head
while curr is not None:
result.append(curr.data)
curr = curr.next
return result
def solution(x):
return 0
- 두 리스트의 연결
- 연결 리스트 self의 뒤에
- 또다른 연결 리스트인 L을 이어 붙임
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 <= 0 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = pos.next
i += 1
return curr
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
def concat(self, L):
self.tail.next = L.head
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount
- 연결리스트가 힘을 발휘할 때
- 삽입과 삭제가 유연하다는 것이 가장 큰 장점
- 특정 pos 뒤에 삽입 삭제를 한다 헀을때 리스트를 다음과 같이 변형시킨다.(앞에 dummy node를 추가)
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
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 traverssal(self):
result = []
curr = self.head
while curr.next:
curr = curr.next
result.append(curr.data)
return result
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 traverssal(self):
result = []
curr = self.head
while curr.next:
curr = curr.next
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount + 1:
return None
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
- 원소의 삽입
- prev가 가리키는 node의 다음에
- newNode를 삽입하고
- 성공/실패에 따라 True/False를 리턴
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 traverssal(self):
result = []
curr = self.head
while curr.next:
curr = curr.next
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount + 1:
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
- 메서드 InsertAt() 의 구현
- pos 범위 조건
- pos == 1인 경우에는 head뒤에 node 삽입
- pos == nodeCount + 1인 경우는 prev <- tail
- 그렇지 않은 경우는 prev <- getAt()
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 traverssal(self):
result = []
curr = self.head
while curr.next:
curr = curr.next
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount + 1:
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)
- 연결 리스트 연산 - 원소의 삭제
- prev의 다음 node를 삭제하고
- 그 node의 data를 리턴
- 주의 사항
- prev가 마지막 node일때 (prev.next == None)
- 리스트 맨 끝의 node를 삭제할 때 (curr.next == None)
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 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 popAfter(self, prev):
if prev == self.tail:
return None
curr = prev.next
prev.next = curr.next
if curr.next == None:
self.tail = prev
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
else:
prev = self.getAt(pos-1)
return self.popAfter(prev)
def solution(x):
return 0
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 traverssal(self):
result = []
curr = self.head
while curr.next:
curr = curr.next
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount + 1:
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
