Python-연결된 목록

연결 목록은 연결을 통해 함께 연결되는 일련의 데이터 요소입니다. 각 데이터 요소는 포인터 형태의 다른 데이터 요소에 대한 연결을 포함합니다. Python은 표준 라이브러리에 연결 목록이 없습니다. 이전 장에서 설명한 노드 개념을 사용하여 연결 목록 개념을 구현합니다. 우리는 이미 노드 클래스를 생성하는 방법과 노드의 요소를 횡단하는 방법을 보았습니다. 이 장에서 우리는 단일 연결 목록으로 알려진 연결 목록의 유형을 연구 할 것입니다. 이 유형의 데이터 구조에서는 두 데이터 요소 사이에 하나의 링크 만 있습니다. 이러한 목록을 만들고 목록에서 요소를 삽입, 업데이트 및 제거하는 추가 메서드를 만듭니다.

연결 목록 생성

연결 목록은 지난 장에서 배운 노드 클래스를 사용하여 생성됩니다. Node 객체를 만들고이 ode 객체를 사용할 다른 클래스를 만듭니다. 노드 객체를 통해 적절한 값을 전달하여 다음 데이터 요소를 가리 킵니다. 아래 프로그램은 세 가지 데이터 요소로 연결된 목록을 만듭니다. 다음 섹션에서는 연결 목록을 탐색하는 방법을 살펴 보겠습니다.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

링크 된 목록 탐색

단일 연결 목록은 첫 번째 데이터 요소에서 시작하는 방향으로 만 순회 할 수 있습니다. 다음 노드의 포인터를 현재 데이터 요소로 지정하여 다음 데이터 요소의 값을 인쇄합니다.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

Mon
Tue
Wed

연결된 목록에 삽입

링크 된 목록에 요소를 삽입하려면 기존 노드에서 새로 삽입 된 노드로 포인터를 다시 할당해야합니다. 새 데이터 요소가 연결 목록의 시작 또는 중간 또는 끝에 삽입되는지 여부에 따라 다음 시나리오가 있습니다.

연결된 목록의 시작 부분에 삽입

여기에는 새 데이터 노드의 다음 포인터가 연결된 목록의 현재 헤드를 가리키는 것이 포함됩니다. 따라서 링크드리스트의 현재 헤드가 두 번째 데이터 요소가되고 새 노드가 링크드리스트의 헤드가됩니다.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval
    def AtBegining(self,newdata):
        NewNode = Node(newdata)

# Update the new nodes next val to existing node
        NewNode.nextval = self.headval
        self.headval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtBegining("Sun")

list.listprint()

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

Sun
Mon
Tue
Wed

링크 된 목록 끝에 삽입

여기에는 링크드리스트의 현재 마지막 노드의 다음 포인터가 새 데이터 노드를 가리키는 것이 포함됩니다. 따라서 링크드리스트의 현재 마지막 노드는 두 번째 마지막 데이터 노드가되고 새 노드는 링크드리스트의 마지막 노드가됩니다.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add newnode
    def AtEnd(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtEnd("Thu")

list.listprint()

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

Mon
Tue
Wed
Thu

두 데이터 노드 사이에 삽입

여기에는 특정 노드의 포인터를 추적하여 새 노드를 가리 킵니다. 이는 새 노드와 새 노드가 삽입 될 기존 노드를 모두 전달함으로써 가능합니다. 그래서 우리는 새로운 노드의 다음 포인터를 중간 노드의 다음 포인터로 변경할 추가 클래스를 정의합니다. 그런 다음 새 노드를 중간 노드의 다음 포인터에 할당합니다.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add node
    def Inbetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return

        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")

list.headval.nextval = e2
e2.nextval = e3

list.Inbetween(list.headval.nextval,"Fri")

list.listprint()

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

Mon
Tue
Fri
Thu

좋아요 목록에서 항목 제거

해당 노드의 키를 사용하여 기존 노드를 제거 할 수 있습니다. 아래 프로그램에서 삭제할 노드의 이전 노드를 찾습니다. 그런 다음이 노드의 다음 포인터를 삭제할 노드의 다음 노드를 가리 킵니다.

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class SLinkedList:
    def __init__(self):
        self.head = None

    def Atbegining(self, data_in):
        NewNode = Node(data_in)
        NewNode.next = self.head
        self.head = NewNode
		
# Function to remove node
    def RemoveNode(self, Removekey):

        HeadVal = self.head

        if (HeadVal is not None):
            if (HeadVal.data == Removekey):
                self.head = HeadVal.next
                HeadVal = None
                return

        while (HeadVal is not None):
            if HeadVal.data == Removekey:
                break
            prev = HeadVal
            HeadVal = HeadVal.next

        if (HeadVal == None):
            return

        prev.next = HeadVal.next

        HeadVal = None

    def LListprint(self):
        printval = self.head
        while (printval):
            print(printval.data),
            printval = printval.next


llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

Thu
Wed
Mon