1. 연결 리스트
배열을 삽입하고 삭제하는 시간 복잡도는 O(N)입니다.
삽입과 삭제가 흔한 상황에서 단순한 배열은 배열의 요소 수가 매우 많을 때 비효율적입니다.
이 문제를 해결하는 것으로 보이는 데이터 구조 중 하나는 연결 목록입니다.
연결 목록 검색은 느리지만(O(N)) 삽입 및 삭제 작업은 매우 빠릅니다(O(1)).
따라서 삽입과 삭제가 빈번한 경우 연결 리스트를 사용하면 효과적으로 문제를 해결할 수 있다.
2. 매듭
노드는 데이터가 저장되는 장소입니다.
연결된 목록은 여러 노드의 모음입니다.
연결된 목록에서 한 노드에는 데이터와 다른 노드에 대한 경로가 있습니다.
노드를 정의하는 방식에 따라 앞뒤로 이동할 수 있습니다.
3. 단일 연결 리스트
단일 연결 리스트는 단방향 연결 방향이 있는 연결된 목록오전.
여기 각 노드에는 데이터와 다음 값이 있습니다.
여기서 데이터는 값이고 다음은 다음 노드의 위치입니다.
~을 참고하여
다음과 같이 3이 있는 노드가 있습니다.
다음 노드가 존재하지 않으므로 next는 기본적으로 null을 포함합니다.
Python을 사용하여 이러한 노드를 생성할까요?
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
node1 = Node(3)
"""
node1 = Node()
node1.data = 3
"""
이렇게 생성된 노드 위에 값이 5인 새 노드 node2를 생성합니다.
여기서 우리는 node1이 node2를 가리키기를 원합니다.
node1.next = 노드2.
node2 = Node(5)
node1.next = node2
node1.next = node2는 node1의 next가 가리키는 노드가 node2 자신임을 의미합니다.
그래서 이런 식으로 인쇄하면…
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
node1 = Node(3)
node2 = Node(5)
node1.next = node2
print(node2.data)
print(node1.next.data)
5
5
노드1과 노드2 다시 연결을 끊고 싶다면.. 그냥 node1.next = None그냥 넣어
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
node1 = Node(3)
node2 = Node(5)
node1.next = node2
print(node2.data)
print(node1.next.data)
node1.next = None
print(node1.next.data)
지금까지 우리는 간단한 연결 리스트를 만드는 방법을 배웠습니다.
도대체 그게 뭐가 문제야 출발점이 어디입니까?
숫자 3으로 시작하면 숫자 1이나 숫자 2가 표시되지 않습니다.
따라서 시작점은 단일 연결 목록의 선두로 지정되어야 합니다.
그리고 꼬리에 연결 리스트가 어디까지 연결되어 있는지 지정하는 것이 좋습니다.
Head to Tail 검색은 삽입과 삭제의 경우를 제외하고 모든 요소를 하나씩 확인하므로 O(N) 시간이 소요됩니다.
이 시점에서 연결(삽입) 또는 연결 해제(삭제)만 하면 되므로 O(1)입니다.
(물론 어디를 붙여넣거나 지워야할지 모르겠다면. 위치를 찾는데 시간이 좀 걸리면 O(N)이 됩니다.
)
또한 단일 연결 목록은 단방향입니다.
그래서 찾기 위해 앞으로 가면 뒤로 갈 수 없습니다.
뒷부분을 보고 싶으면 다시 하셔야 합니다.
4. 연결 리스트 삽입
꼬리 뒤에 값을 삽입한다고 가정합니다.
뒤쪽에 빈 공간이 더 있습니다.
새로운 노드가 들어오면 next가 가리키는 노드를 해당 노드라고 합니다.
이렇게 하면 연결 처리가 큰 문제가 됩니다.
그러나 일단 연결되면 이제 꼬리가 새로 생성된 노드입니다.
그래서 꼬리가 무엇인지 보여주는 부분을 바꿔야 합니다.
구현이 좀 이상한 것 같아요.. 이런거요?
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
SLL.tail.next = new_node
#현재 tail을 변경한다
SLL.tail = new_node
마찬가지로 헤드 앞에 새 값을 추가하면 새 노드가 생성되고 헤드 옆의 노드가 연결됩니다.
현재 헤드를 새로 생성된 노드로 변경
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
self.tail.next = new_node
#현재 tail을 변경한다
self.tail = new_node
def insert_front(self,num):
#새로운 노드를 만든다
new_node = Node(num)
#새로운 노드의 next를 head에 연결
new_node.next = self.head
#현재 head를 새로운 노드로 변경
self.head = new_node
그러나 헤드 바로 뒤에 노드를 추가하는 것은 어떻습니까?
먼저 새 노드를 만듭니다.
새 노드의 다음 값을 헤드의 다음 값에 연결
이제 head의 다음 값을 새로 생성된 노드로 변경합니다.
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
self.tail.next = new_node
#현재 tail을 변경한다
self.tail = new_node
def insert_front(self,num):
#새로운 노드를 만든다
new_node = Node(num)
#새로운 노드의 next를 head에 연결
new_node.next = self.head
#현재 head를 새로운 노드로 변경
self.head = new_node
def insert_after_head(self,num):
#새로운 노드 만들기
new_node = Node(num)
#새로운 노드의 next를 head의 next에
new_node.next = self.head.next
#현재 head의 next를 새로운 노드에
self.head.next = new_node
5. 연결 리스트 삭제
삽입은 새로운 연결을 정의하지만 삭제는 제거해야 합니다.
삭제할 노드 바로 앞의 노드에서 삭제할 때는 다음 노드로 이동해야 하므로 주의하세요.요점
예를 들어 꼬리를 삭제하는 프로세스를 고려하십시오.
중간 파란색 매듭을 삭제하고 다음으로 해야 할 일은 머리 부분에서 꼬리로 전환하는 것입니다.
머리는 어떻게 지우나요?
head의 값을 head.next로 변경하면 완료됩니다.
이 경우 실제로 노드를 삭제하지 않더라도 이렇게 노드가 삭제된 것처럼 보입니다.
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
self.tail.next = new_node
#현재 tail을 변경한다
self.tail = new_node
def insert_front(self,num):
#새로운 노드를 만든다
new_node = Node(num)
#새로운 노드의 next를 head에 연결
new_node.next = self.head
#현재 head를 새로운 노드로 변경
self.head = new_node
def insert_after_head(self,num):
#새로운 노드 만들기
new_node = Node(num)
#새로운 노드의 next를 head의 next에
new_node.next = self.head.next
#현재 head의 next를 새로운 노드에
self.head.next = new_node
def delete_front(self):
#현재 head를 head.next로 변경
self.head = self.head.next
인수로 전달된 num 값과 일치하는 노드를 찾아 삭제하는 삭제 함수를 고려하십시오.
먼저 머리를 찾아라
그런 다음 주어진 번호로 노드 검색을 시작합니다.
현재 노드의 다음 노드의 데이터가 num이 아닌 경우…
다음 노드로 넘어가도 괜찮으니 현재 노드를 다음 노드인 node.next로 변경합니다.
어떻게든 다음 노드의 데이터가 num… 즉, node.next.data == num…이면
루프를 종료하고 node.next를 삭제하십시오.
node.next를 어떻게 삭제합니까?
node.next를 node.next.next로 바꾸세요!
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
self.tail.next = new_node
#현재 tail을 변경한다
self.tail = new_node
def insert_front(self,num):
#새로운 노드를 만든다
new_node = Node(num)
#새로운 노드의 next를 head에 연결
new_node.next = self.head
#현재 head를 새로운 노드로 변경
self.head = new_node
def insert_after_head(self,num):
#새로운 노드 만들기
new_node = Node(num)
#새로운 노드의 next를 head의 next에
new_node.next = self.head.next
#현재 head의 next를 새로운 노드에
self.head.next = new_node
def delete_front(self):
#현재 head를 head.next로 변경
self.head = self.head.next
#인자로 받아온 num을 가지는 노드를 삭제(항상 존재하고, head,tail이 아니다)
def delete(self,num):
node = self.head
while node.next.data !
= num:
node = node.next
node.next = node.next.next
6. 연결 리스트 검색
삽입 및 삭제 시 헤드와 테일이 계속 바뀌는 이유는 탐색을 쉽게 하기 위함입니다.
오전.
단일 연결 리스트에서는 처음부터 끝을 설정해야 하므로 머리부터 시작하여 꼬리가 나올 때까지 계속 따라가면서 검색을 계속할 수 있습니다.
7. 운동
오름차순으로 정렬된 두 개의 연결된 목록을 하나로 결합하고 결합된 결과도 정렬하려면 어떻게 해야 할까요?
def solution(SLL1, SLL2):
result = SLL()
#두 연결리스트의 head를 가져오고
node1 = SLL1.head
node2 = SLL2.head
while node1 !
= null or node2 !
= null:
#node2가 없거나, node1이 존재하고, node1의 데이터가 node2보다 작다면
if node2 == null or (node1 !
= null and node1.data < node2.data):
#node1의 데이터를 먼저 넣고
result.insert_end(node1.data)
#node1의 head 이동
node1 = node1.next
else: #node2의 데이터가 node1의 데이터보다 작다면..
#node2의 데이터를 넣고
result.insert_end(node2.data)
#node2의 head이동
node2 = node2.next
return result
다음 코드의 출력을 나열하십시오..?
def solution():
sll = SLL()
sll.insert_front(15)
sll.insert_front(25)
sll.insert_end(20)
sll.insert_front(45)
sll.insert_end(30)
node = sll.head
while node !
= null
print(node.data)
node = node.next
아무 것도 없는 연결 리스트에 15를 넣으면…
이 연결 리스트의 헤드 앞에 25를 넣으면…
꼬리 뒤에 20을 넣으면…? 25 > 15 > 20
머리 앞에 45를 대면…? 45 > 25 > 15 > 20
꼬리 뒤에 30을 넣으면…?
