링크드 리스트
연결된 구조로 되었있음
노드로 구성되어 있는데 노드에는 링크필드와 데이터 필드가 있음
- 링크필드 다른 노드들과 연결시켜주는 부분으로 다른 객체의 주소값이 들어있다.
- 데이터 필드 저장하려는 데이터들이 위치하는 필드
연결리스트는 용량이 고정되어있지 않다.
데이터의 삽입과 삭제연산이 O(1) 걸린다
n 번째 데이터에 접근하는 시간이 O(n) 만큼걸린다.
- 헤드 포인터 링크드 리스트에서 첫번째 요소를 연결하는 주소값을 가지고 있는 부분
연결 리스트의 종류
- 단순연결리스트 - 단방향으로 연결되어있어서 연결된 링크가 하나이고 마지막 요소의 링크는 None을 가진다.
- 원형연결리스트 - 단순연결리스트와 본질적으로 동일하지만 마지막 노드가 헤드와 연결된 첫번째 노드를 가르키게 만들어짐
- 이중연결리스트 - 선행노드와 후행노드에 왔다갔다 이동이 가능하게 만들어진 연결리스트이다 하나의 노드에 링크가 2개가 배정된다.
연결 리스트를 이용한 스택의 구현
from node import node
class linkedStack:
def __init__(self):
self.top = None # 헤드 포인터 원래 첫번째 요소랑 연결되어있음
def isEmpty(self):
return self.top == None
def clear(self):
self.top = None
def push(self, data):
if self.top != None:
self.top = node(data, self.top) # 원래top 랑 연결되어있는 연결을 새로운 노드를 생성하면서
# 새로운 노드가 원래 첫번째 요소를 연결되게 만든다.
else:
self.top = node(data, None)
def pop(self):
if not self.isEmpty():
n = self.top
self.top = n.link
return n.data
else:
return None
def peek(self):
return self.top.data
def size(self):
start = self.top
count = 0
while start != None:
start = start.link
count += 1
return count
def display(self):
if self.top == None:
return None
else:
start = self.top
while start != None:
print(start.data, end="->")
start = start.link
print()
start = self.top
count = 0
while start != None:
start = start.link
count += 1
return count
음 이렇게 코딩하는 방식을 조금 기억해야할 필요가 있는거 같다 링크드 리스트 전체를 돌아보려면 node의 링크를 타도 돌아니다가 마지막 노드를 알아보는 방법은 마지막 노드의 링크에 None값이 들어있으면 마지막 노드니까 그동안 돌아다니면서 쌓은 count를 반환한다.
위와 같은 방식은 display() 함수를 만들때도 사용하는데 O(n)이다.
def push(self, data):
if self.top != None:
self.top = node(data, self.top) # 원래top 랑 연결되어있는 연결을 새로운 노드를 생성하면서
# 새로운 노드가 원래 첫번째 요소를 연결되게 만든다.
else:
self.top = node(data, None)
링크드 스택에 넣는 법은 존나 간단하다 데이터랑 self.top 에 저장되어있던 주소값을사용해서 원래 첫번째 노드를 새로 들어가는 node가 가르킬 수 있게 만들어 준다 그리고 self.top에 새로 만들어진 node의 주서값을 넣어준다
근데 이때 주의 해야할 점이
맨첨에 삽입할때는 self.top가 가르키는 값이 None이므로 위와 같이코딩해야 할 것 같지만 사실은
self.top = node(data, self.top)그냥 이렇게 갈겨도 처음에 self.top이 None값을 가질때도 상관없이 존나 잘돌아간다.
시간복잡도는 O(1) 삽입, 삭제
O(n), 크기랑, display할때 근데 크기는 생성할때 stack 이랑는 size안에서 생성해서 push가 일어날때 증가시키고 pop가 호출될 때 감소시키면 시간 복잡도는 낮아진다,\
단순 링크드 리스트
from node import node as Node
class linkedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def clear(self):
self.head = None
def size(self):
if not self.isEmpty():
start = self.head
count = 0
while start != None:
start = start.link
count += 1
return count
else:
return 0
def display(self, msg="linkedlist"):
start = self.head
print(msg, end=":")
if self.isEmpty():
print("None")
while start != None:
print(start.data, end=" ->")
start = start.link
print("None")
def getNode(self, pos):
if pos < 0:
return None
else:
node = self.head
while pos > 0 and node != None:
node = node.link
pos -= 1
return node
# if self.isEmpty():
# return None
# index = 0 # 시작하는 index = 0
# node = self.head
# while index != pos:
# node = node.link
# index += 1
# return node
def getEntry(self, pos): # pos에 있는 노드의 데이터 반환
if not self.isEmpty():
node = self.head
while pos > 0 and node != None: # 주어진 인덱스 번 연사을 해야한다
node = node.link
pos -= 1
return node.data
def replace(self, pos, elem): # pos 에 있는 data 를 elem으로 교체
if pos < 0:
return None
else:
node = self.head
while pos > 0 and node != None:
node = node.link
node.data = elem # pos 의 위치에 있는 node를 교체함
def find(self, value): # value 를 가진 node의 인덱스를 반환
node = self.head
while node.data != value:
node = node.link
return node
def insert(self, pos, elem):
before = self.getNode(pos - 1)
if before == None: # pos -1 이 0 보다 작다는 거고 그러면 pos 가 0이라는거
if self.head == None: # head가 가르키는 노드가 없고 처음 삽입하는 거지
self.head = Node(elem, None) # 처음이자 마지막 노드를 생성
else:
self.head = Node(elem, self.head.link)
else:
# pos -1 .link 를 link 로 가지는 새로운 node 생성
before.link = Node(elem, before.link) # 이 새로 pos 다음의 노드와 연결된거임
def delete(self, pos): # pos에 있는 노드 삭제
if self.isEmpty():
return
else:
before = self.getNode(pos - 1) # 삭제하려는 전노를 찾음
if before == None: # 노가의 index가 0이라서 getNode(pos -1) 을 실행하면 None 을 반환하니까 None이면 첫번째 node를 삭제하라고 한거임
self.head = self.head.link
else:
before.link = before.link.link
s = linkedList()
s.display()
for i in range(10):
s.insert(i, i * 10)
s.display()
s.insert(s.size(),1000)
s.display()
for i in range(5):
s.delete(i)
s.display()유심히 봐야될거는 각함수의 ADT의 기능 그리고 함수 3개 정도
def getNode(self, pos):
if pos < 0:
return None
else:
node = self.head
while pos > 0 and node != None:
node = node.link
pos -= 1
return node
pos에 해당하는 노드를 반환하는 함수임 근데 이게 이어지는 이유가 있으
def insert(self, pos, elem):
before = self.getNode(pos - 1)
if before == None: # pos -1 이 0 보다 작다는 거고 그러면 pos 가 0이라는거
if self.head == None: # head가 가르키는 노드가 없고 처음 삽입하는 거지
self.head = Node(elem, None) # 처음이자 마지막 노드를 생성
else:
self.head = Node(elem, self.head.link)
else:
# pos -1 .link 를 link 로 가지는 새로운 node 생성
before.link = Node(elem, before.link) # 이 새로 pos 다음의 노드와 연결된거임 def delete(self, pos): # pos에 있는 노드 삭제
if self.isEmpty():
return
else:
before = self.getNode(pos - 1) # 삭제하려는 전노를 찾음
if before == None: # 노가의 index가 0이라서 getNode(pos -1) 을 실행하면 None 을 반환하니까 None이면 첫번째 node를 삭제하라고 한거임
self.head = self.head.link
else:
before.link = before.link.link
위에 두개 연산을 실행할 때 많이 쓰는 레퍼토리가 getNode(pos-1) 인데 이걸 왜하내면 첨가하고 삭제하기 위해서는 해당pos의 하나 전의 인덱스의 노드를 아는 것이 제일 쉬운 방법이기 때문이다 근데 이때 pos = 0이면 가장 첫번째 요소를 삭제하거 빼는 연산인데 이때 before가 0 이 되는 이유는 if pos < 0: return None 이거 때문이다 그래서 before은 getNode(-1) 는 그래서 None 을 반환한다.
그래서 이렇게 만들면 병신같이 인덱스를 - 값만 넣어 주어도 헤더가 앞으로 이동하면서 값을 삭제하는 연산을 실행한다.
reverse 함수 재귀적으로 호출하는 방법
def reverse_print(self, node):
if node.link == None:
print("None")
return
self.reverse_print(node.link)
print(node.data, end=" <-")위는 재귀함수를 이용해서 구현한 리벌스 함수이다 . 여기서 주의해야할 점이 브레이크 포인터 설정인데 이를 구현하기 위해서는 꼭 브레이크 포인트를 재귀함수 호출전에 호출해서 NONE 타임 객체로 인해서 함수가 호출되지 않게 만들어야한다.
