파이썬의 연결 리스트
- Python에서 연결 목록이란 무엇입니까?
- Python에서 연결 목록을 만드는 방법
- Python에서 연결 목록의 모든 요소 인쇄
- Python의 연결 목록에 요소 삽입
- Python의 연결 목록에서 요소 삭제
- Python에서 연결 목록의 요소 수 계산
- Python의 연결 목록에서 노드 업데이트
- Python에서 연결 목록을 사용하는 이유
- Python의 전체 구현 연결 목록
- 결론
Python은 다양한 내장 데이터 구조를 제공합니다.
그러나 각 데이터 구조에는 제한 사항이 있습니다. 이 때문에 맞춤형 데이터 구조가 필요합니다.
이 문서에서는 연결 목록이라는 사용자 지정 데이터 구조에 대해 설명합니다. 또한 Python으로 연결 목록을 구현하고 연결 목록에 대해 다양한 작업을 수행합니다.
Python에서 연결 목록이란 무엇입니까?
이름에서 알 수 있듯이 연결 목록은 링크를 사용하여 연결된 요소를 포함하는 데이터 구조입니다.
연결 리스트는 노드라는 객체를 사용하여 생성됩니다. 각 노드에는 두 개의 속성이 있습니다. 하나는 데이터를 저장하기 위한 것이고 다른 하나는 연결 목록의 다음 노드에 연결하기 위한 것입니다.
다음 그림을 통해 노드의 구조를 이해할 수 있습니다.
여기,
Node는data및next속성을 포함하는 개체입니다.data속성은 데이터를 저장합니다.- 속성
next는 연결 목록의 다음 노드를 나타냅니다.
다음 이미지와 같이 다양한 노드를 연결하여 연결 리스트를 생성할 수 있습니다.
여기,
- 4개의 노드로 구성된 연결 리스트를 만들었습니다.
- 첫 번째 노드는 숫자 10을 포함하고, 두 번째 노드는 20을 포함하고, 세 번째 노드는 30을 포함하고, 마지막 노드는 40을 포함합니다.
- 첫 번째 노드를 참조하는
Head변수도 생성했습니다. 연결 목록 개체에서Head변수만 유지합니다. 다른 모든 노드의 데이터는Head가 참조하는 첫 번째 노드에서 시작하여 연결 목록을 순회하여 얻습니다. - 마지막 노드의
next속성은None개체를 참조합니다. 연결 목록의 마지막 노드에 대한next속성은 항상None개체를 참조합니다. - 연결 목록이 비어 있는 경우
Head변수는None개체를 참조합니다.
이제 연결 목록의 기본 구조를 이해했습니다. 파이썬으로 연결 리스트를 구현해보자.
Python에서 연결 목록을 만드는 방법
노드는 연결 목록의 구성 요소이므로 먼저 노드를 만듭니다. 이를 위해 아래와 같이 data 및 next 속성을 가진 Node 클래스를 정의합니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
myNode = Node(10)
print("The data in the node is:", myNode.data)
print("The next attribute in the node is:", myNode.next)
출력:
The data in the node is: 10
The next attribute in the node is: None
위의 예에서 Node의 next 속성은 기본적으로 None을 참조합니다. 그것을 연결 목록에 삽입할 때 우리는 연결 목록의 노드에 next 속성을 할당합니다.
연결 목록을 생성하려면 Head 속성을 가진 객체를 생성해야 합니다. 아래와 같이 LinkedList 클래스를 정의할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4
print("The elements in the linked list are:")
print(myLinkedList.Head.data, end=" ")
print(myLinkedList.Head.next.data, end=" ")
print(myLinkedList.Head.next.next.data, end=" ")
print(myLinkedList.Head.next.next.next.data)
출력:
The linked list is:
10 20 30 40
위의 예에서는 연결 목록을 만들었습니다.
그 후 주어진 데이터를 이용하여 수동으로 노드를 생성하여 연결 리스트에 하나씩 추가하고 출력하였다. 나중에 파이썬의 while 루프를 사용하여 연결 목록에 요소를 삽입하는 방법을 배웁니다.
이제 모든 노드에 수동으로 액세스하지 않고 연결 목록의 모든 요소를 인쇄하는 방법에 대해 논의하겠습니다.
Python에서 연결 목록의 모든 요소 인쇄
모든 연결 목록 요소를 인쇄하기 위해 while 루프를 사용합니다.
Head 포인터에서 시작하여 먼저 노드의 data 속성을 사용하여 현재 노드의 데이터를 인쇄합니다. 그런 다음 next 포인터를 사용하여 다음 노드로 이동합니다.
연결 목록의 끝에 도달할 때까지 이 프로세스를 따릅니다(즉, 노드의 next 속성이 None인 것으로 확인됨). 아래와 같이 printList() 메소드에서 전체 로직을 구현할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
10 20 30 40
Python의 연결 목록에 요소 삽입
연결 리스트에 요소를 삽입할 때 네 가지 상황이 있습니다.
- 연결 리스트는 삽입 전에 비워둘 수 있습니다.
- 비어 있지 않은 연결 목록의 시작 부분에 요소를 삽입해야 합니다.
- 연결 리스트의 끝에 요소를 삽입해야 합니다.
- 연결 리스트에서 주어진 위치에 요소를 삽입해야 합니다.
모든 상황에서 연결 목록에 요소를 삽입하는 방법에 대해 논의해 보겠습니다.
빈 연결 목록에 요소 삽입
빈 연결 목록에 요소를 삽입하려면 요소를 입력 인수로 받아들이고 연결 목록에 입력 요소를 포함하는 노드를 추가하는 insertIntoEmptyList() 메서드를 정의합니다.
이를 위해 입력 요소를 data로 사용하여 insertIntoEmptyList()에 노드를 생성합니다. 노드를 생성한 후 Head 속성에 노드를 할당합니다.
이런 식으로 새 노드는 연결 목록의 첫 번째 노드가 됩니다. 이 방법은 다음과 같이 구현할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertIntoEmptyList(self, element):
newNode = Node(element)
self.Head = newNode
myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
10
연결 목록의 시작 부분에 요소 삽입
비어 있지 않은 목록의 시작 부분에 요소를 삽입하려면 요소를 입력으로 받아 연결 목록의 시작 부분에 추가하는 insertAtBeginning() 메서드를 정의합니다. insertAtBeginning() 메서드에서 먼저 입력 요소를 데이터로 사용하여 노드를 생성합니다.
그런 다음 새로 생성된 노드의 next 속성을 연결 목록의 Head 속성이 가리키는 노드를 가리킵니다. 다음으로 새로 생성된 노드를 Head 속성에 할당합니다.
이런 식으로 새 노드는 연결 목록의 시작 부분에 삽입됩니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertIntoEmptyList(self, element):
newNode = Node(element)
self.Head = newNode
def insertAtBeginning(self, element):
newNode = Node(element)
newNode.next = self.Head
self.Head = newNode
myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
30 20 10
아래와 같이 위의 방법을 결합하여 연결 목록의 시작 부분에 요소를 삽입하는 단일 방법을 만들 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertAtBeginning(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
newNode = Node(element)
newNode.next = self.Head
self.Head = newNode
myLinkedList = LinkedList()
myLinkedList.insertAtBeginning(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
30 20 10
빈 연결 목록에 삽입하는 것은 본질적으로 연결 목록의 시작 부분에 요소를 삽입한다는 것을 의미하기 때문에 insertIntoEmptyList() 메서드를 insertAtBeginning() 메서드로 병합했습니다.
연결 목록 끝에 요소 삽입
빈 목록 끝에 요소를 삽입하는 것은 연결 목록의 시작 부분에 요소를 삽입하는 것과 유사합니다.
연결 목록의 끝에 요소를 삽입하려면 먼저 연결 목록이 비어 있는지 확인합니다. 연결 목록이 비어 있는 것으로 확인되면 insertAtBeginning() 메서드에서와 같이 Head 속성에 새 요소를 포함하는 노드를 간단히 할당할 수 있습니다.
그렇지 않으면 while 루프를 사용하여 끝까지 연결 목록을 탐색합니다. Head로 시작하여 노드의 next 속성이 None을 가리킬 때까지 노드의 next 속성을 사용하여 다음 노드로 계속 이동할 것입니다.
next 속성이 None을 가리키는 노드에 도달하면 마지막 노드에 있습니다. 이제 입력 데이터를 사용하여 새 노드를 만들고 이 노드를 연결 목록의 마지막 노드의 다음 속성에 할당합니다.
이런 식으로 새 요소가 연결 목록의 끝에 삽입됩니다. 다음과 같이 insertAtEnd() 메소드에서 이 전체 로직을 구현할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertAtEnd(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
current = self.Head
while current.next is not None:
current = current.next
newNode = Node(element)
current.next = newNode
myLinkedList = LinkedList()
myLinkedList.insertAtEnd(10)
myLinkedList.insertAtEnd(20)
myLinkedList.insertAtEnd(30)
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
10 20 30
연결 목록에서 주어진 위치에 요소 삽입
카운터 변수와 while 루프를 사용하여 연결 목록의 주어진 위치에 요소를 삽입합니다.
Head 포인터에서 시작하여 while 루프를 사용하여 다음 노드로 계속 이동합니다. 각 반복에서 카운터 변수도 증가합니다.
주어진 위치 이전의 노드에 도달하면 while 루프를 종료합니다. 또한 연결 목록의 끝에 도달하면 루프를 종료합니다. 그렇지 않으면 프로그램에서 오류가 발생합니다.
그 후에도 여전히 Head에 있으면 연결 목록의 첫 번째 위치에 요소를 추가해야 합니다. 우리는 주어진 위치에 있는 노드를 새로운 노드 요소를 포함하는 next 포인터에 할당할 것입니다. 다음으로 새 요소의 노드를 연결 목록의 Head에 할당합니다.
첫 번째 위치에 요소를 삽입할 필요가 없다면 주어진 위치에 있는 노드를 새 요소를 포함하는 노드의 next 포인터에 할당합니다. 다음으로 position-1에 있는 노드의 next 속성에 새 노드를 할당합니다.
이런 식으로 새 요소가 지정된 위치에 삽입됩니다. 아래와 같이 insertAtPosition() 메소드에서 전체 로직을 구현할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(20, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(30, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
10
The elements in the linked list are:
10 20
The elements in the linked list are:
10 20 30
The elements in the linked list are:
10 40 20 30
Python의 연결 목록에서 요소 삭제
연결 목록에서 요소를 삭제하려고 할 때 세 가지 상황이 있을 수 있습니다.
- 연결 리스트의 첫 번째 요소를 삭제해야 합니다.
- 연결 리스트의 마지막 요소를 삭제해야 합니다.
- Linked list의 어느 위치에서든 요소를 삭제해야 합니다.
이 모든 경우를 하나씩 논의해 보겠습니다.
연결 목록의 첫 번째 요소 삭제
연결 목록의 첫 번째 요소를 삭제하려면 먼저 연결 목록이 비어 있는지 확인합니다.
이를 위해 연결 목록의 Head가 None을 가리키는지 확인합니다. 그렇다면 연결 목록이 비어 있고 삭제할 요소가 없음을 사용자에게 알립니다.
그렇지 않으면 첫 번째 노드를 임시 변수에 할당합니다. 그런 다음 연결 목록의 두 번째 노드를 Head 속성에 할당합니다.
그런 다음 del 문을 사용하여 임시 변수에 저장된 첫 번째 노드를 삭제합니다. 아래와 같이 deleteFromBeginning() 메소드에서 전체 로직을 구현할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteFromBeginning(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
node = self.Head
self.Head = self.Head.next
del node
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
40 20 30
The elements in the linked list are:
20 30
연결 목록의 마지막 요소 삭제
연결 목록의 마지막 요소를 삭제하려면 먼저 연결 목록이 비어 있는지 확인합니다.
이를 위해 연결 목록의 Head가 None을 가리키는지 확인합니다. 그렇다면 연결 목록이 비어 있고 삭제할 요소가 없음을 사용자에게 알립니다.
목록에 요소가 있는 경우 다음 프로세스를 따릅니다.
- 첫 번째 노드를
current변수에 할당합니다. 이전변수를없음으로 초기화합니다.while루프를 사용하여 연결 목록을 탐색하고current변수의 노드를previous변수에 할당하고current변수가 마지막 노드에 도달할 때까지current변수를 다음 노드로 진행합니다. . 이 경우current에 할당된 노드의next속성은None이 됩니다.- 현재 변수가 마지막 노드에 도달하면
이전변수의다음속성에없음을 할당하고현재변수에 할당된 노드를 삭제합니다.
위의 단계를 실행하여 연결 목록의 마지막 요소를 삭제할 수 있습니다. 아래와 같이 deleteFromLast() 메소드에서 전체 로직을 구현할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteFromLast(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
while current.next is not None:
previous = current
current = current.next
previous.next = None
del current
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
10 40 20
The elements in the linked list are:
10 40
연결 목록의 지정된 위치에서 요소 삭제
연결 목록의 주어진 위치에서 요소를 삭제하려면 먼저 연결 목록이 비어 있는지 확인합니다.
이를 위해 연결 목록의 Head가 None을 가리키는지 확인합니다. 그렇다면 연결 목록이 비어 있고 삭제할 요소가 없음을 사용자에게 알립니다.
연결 목록에 요소가 있고 다른 위치에서 요소를 삭제해야 하는 경우 다음 단계를 따릅니다.
- 첫 번째 노드를
current변수에 할당합니다. 이전변수를없음으로 초기화합니다.count변수를 1로 초기화합니다.while루프를 사용하여 연결된 리스트를 탐색하고, 각 반복에서count를 증가시키며current변수의 노드를previous에 할당하고current변수를 다음 노드로 이동합니다. 이를count변수가 삭제할 요소의position에 도달하거나 연결된 리스트의 끝에 도달할 때까지 반복합니다. 이 시점에서current변수는 삭제해야 할 노드를 가리키게 됩니다.- 카운트가 삭제할 요소의 위치와 같아지면 두 가지 상황이 있을 수 있습니다.
- 우리가 여전히
Head에 있는 경우 첫 번째 위치에서 현재 변수의next속성이 참조하는 노드를Head속성에 할당합니다. 그런 다음current변수를 삭제합니다. - 우리가 첫 번째 위치에 있지 않다면
현재변수의 다음 노드를이전변수에 할당된 노드의 다음 속성에 할당합니다.current변수에 할당된 노드를 삭제합니다. 이런 식으로 주어진 위치의 요소가 삭제됩니다.
아래에 설명된 deleteAtPosition() 메서드에서 위의 논리를 구현할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteAtPosition(self, position):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
count = 1
while current.next is not None and count < position:
previous = current
current = current.next
count += 1
if current == self.Head:
self.Head = current.next
del current
else:
previous.next = current.next
del current
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(2)
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
40 20 30
The elements in the linked list are:
40 30
Python에서 연결 목록의 요소 수 계산
연결 목록의 요소 수를 계산하려면 count 변수를 0으로 초기화하기만 하면 됩니다.
그런 다음 Head에서 시작하여 연결 목록의 끝에 도달할 때까지 while 루프를 사용하여 다음 노드로 이동합니다. while 루프의 각 반복에서 count를 1씩 증가시킵니다.
while 루프를 실행한 후 count 변수에 연결된 목록의 요소 수를 갖게 됩니다. 아래 countElements() 메서드와 같이 이 논리를 구현할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def countElements(self):
count = 0
current = self.Head
while current is not None:
count += 1
current = current.next
print("Number of elements in the linked list are:", count)
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.countElements()
출력:
The elements in the linked list are:
10 40 20 30
Number of elements in the linked list are: 4
Python의 연결 목록에서 노드 업데이트
연결 목록에서 노드의 값을 업데이트하는 두 가지 상황이 있을 수 있습니다.
- 값을 바꿔야 합니다.
- 연결 목록의 주어진 위치에 있는 요소에 새 값을 할당해야 합니다.
연결 목록에서 값 바꾸기
연결 목록의 값을 바꾸기 위해 첫 번째 노드에서 시작하여 while 루프를 사용하여 연결 목록을 탐색합니다.
현재 노드에 각 노드에서 대체할 값이 포함되어 있는지 확인합니다. 그렇다면 현재 노드의 값을 새 값으로 바꿉니다.
이런 식으로 replaceElement() 메서드에서 볼 수 있듯이 연결 목록에서 첫 번째로 나타나는 요소를 업데이트할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def replaceElement(self, old_element, new_element):
current = self.Head
while current is not None:
if current.data == old_element:
current.data = new_element
break
current = current.next
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(30, 100)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(20, 150)
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
10 40 20 100
The elements in the linked list are:
10 40 150 100
연결 목록의 주어진 위치에서 요소 업데이트
연결 목록의 주어진 위치에 있는 요소를 업데이트하려면 먼저 연결 목록이 비어 있는지 확인합니다. 그렇다면 두 가지 상황이 있을 수 있습니다.
연결 목록이 비어 있고 첫 번째 위치가 아닌 다른 요소를 업데이트해야 하는 경우 사용자에게 업데이트할 수 없음을 알립니다.
연결 목록이 비어 있고 첫 번째 위치의 요소를 업데이트해야 하는 경우 주어진 요소로 새 노드를 만들고 연결 목록의 Head에 노드를 할당합니다. 그렇지 않으면 counter 변수를 1로 초기화합니다.
그런 다음 while 루프를 사용하여 연결 목록을 탐색합니다. while 루프의 각 반복에서 연결 목록의 다음 노드로 이동하고 counter 변수를 1씩 증가시키고 업데이트해야 하는 요소의 위치에 도달했는지 확인합니다.
업데이트가 필요한 위치에 도달하면 연결 목록의 현재 노드 값을 업데이트하고 사용자에게 알립니다.
업데이트해야 하는 위치에 도달할 수 없고 while 루프가 종료되면 요소가 충분하지 않고 값을 업데이트할 수 없음을 사용자에게 알립니다. 이 로직은 updateAtPosition() 메소드에서 아래와 같이 구현할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def updateAtPosition(self, new_element, position):
if self.Head is None and position != 1:
print("No element to update in the linked list.")
return
elif self.Head is None and position == 1:
newNode = Node(new_element)
self.Head = newNode
return
count = 1
current = self.Head
while current.next is not None and count < position:
count += 1
current = current.next
if count == position:
current.data = new_element
elif current.next is None:
print("Not enough elements in the linked list.")
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(100, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(150, 12)
print("The elements in the linked list are:")
myLinkedList.printList()
출력:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
10 40 100 30
Not enough elements in the linked list.
The elements in the linked list are:
10 40 100 30
Python에서 연결 목록을 사용하는 이유
- 요소에 대한 임의 액세스가 필요하지 않은 경우 연결 목록이 더 나은 대안이 될 수 있습니다. 저장할 수백만 개의 요소가 있고 임의 액세스가 필요하지 않은 경우 Python에서 일반 목록 대신 연결 목록을 사용해야 합니다.
- 목록의 실제 크기는 목록에 있는 요소의 수에 비해 매우 큽니다. 목록의 실제 크기는 목록에 있는 요소 수의 약 1.5배입니다. 목록에 요소를 삽입하기에 충분한 메모리가 있는지 확인합니다. 그러나 연결 목록에는 추가 공백이 필요하지 않습니다.
- 연결 목록에 요소를 삽입할 때 저장소만 필요합니다. 또한 목록에는 연속적인 메모리 위치가 필요합니다. 반대로 연결 목록의 노드는 물리적 메모리의 모든 위치에 존재할 수 있습니다. 참조를 사용하여 연결됩니다.
- 연결 목록을 사용하여 스택 및 큐 데이터 구조를 모두 효율적으로 구현할 수 있습니다. 반면에 목록을 사용하여 대기열을 구현하면 시간 복잡도가 높아집니다.
Python의 전체 구현 연결 목록
다음은 이 기사에서 논의된 모든 방법을 사용하여 Python에서 연결 목록을 구현하기 위한 전체 실행 코드입니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtBeginning(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
newNode = Node(element)
newNode.next = self.Head
self.Head = newNode
def insertAtEnd(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
current = self.Head
while current.next is not None:
current = current.next
newNode = Node(element)
current.next = newNode
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteFromBeginning(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
node = self.Head
self.Head = self.Head.next
del node
def deleteFromLast(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
while current.next is not None:
previous = current
current = current.next
previous.next = None
del current
def deleteAtPosition(self, position):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
count = 1
while current.next is not None and count < position:
previous = current
current = current.next
count += 1
if current == self.Head:
self.Head = current.next
del current
else:
previous.next = current.next
del current
def countElements(self):
count = 0
current = self.Head
while current is not None:
count += 1
current = current.next
print("Number of elements in the linked list are:", count)
def replaceElement(self, old_element, new_element):
current = self.Head
while current is not None:
if current.data == old_element:
current.data = new_element
break
current = current.next
def updateAtPosition(self, new_element, position):
if self.Head is None and position != 1:
print("No element to update in the linked list.")
return
elif self.Head is None and position == 1:
newNode = Node(new_element)
self.Head = newNode
return
count = 1
current = self.Head
while current.next is not None and count < position:
count += 1
current = current.next
if count == position:
current.data = new_element
elif current.next is None:
print("Not enough elements in the linked list.")
결론
이 기사에서는 연결 목록 데이터 구조와 Python에서의 구현에 대해 논의했습니다. 또한 연결 목록에서 다양한 작업을 위한 메서드를 구현했습니다.
이 문서에서는 메서드를 사용하여 모든 작업을 구현했습니다. 연결된 목록의 Head를 입력으로 사용하고 필요한 작업을 실행한 후 헤드를 반환하는 함수를 사용하여 각 작업을 구현할 수도 있습니다.
그러나 실행하는 동안 더 많은 리소스가 필요합니다. 따라서 이 기사에서 사용한 접근 방식을 사용하는 것이 좋습니다.
Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.
GitHub