연결된 목록 파트 1

11399 단어 dsalgo
목록은 메모리에서 분리되지 않은 값이며 인덱스로 찾을 수 있습니다.

메모리:



그러나 Linked List는 분리되어 서로 연결되어 있습니다. 포인터로 하나의 노드를 찾을 수 있습니다.



따라서



빅 오(O)



후드

먼저 이 목록에서 가정하고 노드 4와 7에 대해 알아봅니다.
노드 4에 대해 이야기할 때:


코드에서는 다음과 같습니다.



다시 노드 7의 경우:


이제 포인터 기호로 작업해야 합니다. 숫자 4를 가리키는 방법은 무엇입니까?
7에 4번 블록만 있으면 됩니다.



따라서 실제로 일어나는 일은 다음과 같습니다.



그리고 코드에서:



건설자
이 코드가 어떻게 될 수 있는지 확인하십시오.



여기에서 노드를 생성해야 함을 알 수 있으므로 노드를 생성하기 위한 클래스를 생성합니다. 따라서 생성자 init로 클래스 Node를 생성합니다. 이 클래스는 가치와 다음을 생성합니다.



이제 Linkedlist 클래스로 작업할 수 있습니다.
Node(값)로 노드를 생성하고 이를 헤드로 설정합니다.


또한 꼬리를 해당 노드로 설정합니다.


그런 다음 길이 계산을 유지하십시오.


그래서 우리는 연결된 목록 생성자를 만들었습니다.


이제 4번을 호출하여 연결된 목록을 만듭니다.



이것은 이것을 만들 것입니다 :



연결된 목록 인쇄

모든 클래스에서 이 코드로 연결된 목록을 인쇄할 수 있습니다.

#method under a class
def print_list(self):
    temp=self.head
    while temp != None:
        print(temp.value)
        temp=temp.next


첨부
목록의 끝에 무언가를 추가하면 먼저 빈 연결 목록이 있다고 가정할 수 있으므로 값이 있어야 하고 헤드와 테일 모두를 만들어야 합니다.

목록이 비어 있으므로 아무 것도 없으므로 꼬리와 머리가 없음을 가리킵니다.

이제 우리는 그것을 만들어야 합니다:



따라서 코드는


이미 11,3,23,7이 있는 목록이 있고 목록 끝에 4를 추가해야 하는 경우


우리는 이렇게 했을 것입니다:



#Code for appending 
    def append(self,value):
         new_node=Node(value) #Node is a class
         if self.head is None: #case for empty linked List
             self.head=new_node #making the node head
             self.tail=new_node #making the node tail
         else: #case for already having a value
             self.tail.next=new_node 
             self.tail=new_node
         self.length+=1 
         return True #created for later use 



값 팝
이제 우리는 이것으로 목록을 만들 것입니다


이에:



코드에서는 다음과 같습니다.


이에:


이 코드를 해결하기 위해 pre 및 temp를 가지고 첫 번째 노드를 가리킬 것입니다.


이제 목록을 반복하고 temp.next가 None이 아니면 pre=temp를 설정할 것입니다.
먼저,
임시=임시.다음



그런 다음 temp.next가 None이 아니면 temp=temp.next를 설정하고 pre=temp를 설정합니다.



우리는 temp.next==None 지점까지 계속 그렇게 할 것입니다.



이제 tail을 pre로 설정하겠습니다.


마지막 노드를 중단하기 위해 tail.next를 None으로 설정합니다.


다시, temp는 마지막 노드로 설정되었으므로 해당 노드를 반환하면 완료됩니다!
노드를 성공적으로 팝했습니다.



코드를 작성해 보겠습니다.
사례_1:
빈 목록이 있다고 가정합니다.



def pop(self):
    if self.length==0: #if the list is empty
        return None


사례_2:
콘텐츠가 2개 이상인 경우 다음과 같이 코딩합니다.

while(temp.next): #this will pass if temp.next returns True or 
                  there is a node
     pre=temp
     temp=temp.next


이것은 이것을 바꿀 것입니다 :


이에:



이것은 다음 상황까지 작동합니다.


이제 tail을 pre로 설정하겠습니다.



이제 마지막 노드를 제거하고 tail.next 를 None 으로 설정합니다.



사례_3:
목록에 1개의 노드가 있는 경우:


이제 1을 감소시킨 후 head와 tail을 None으로 설정합니다.


상황을 다음으로 전환:


모든 케이스가 해결되었으므로 이제 온도를 반환합니다. 따라서 노드가 팝됩니다.

#Code for popping
def pop(self):
    if self.length==0: #if the list is empty
        return None
    temp=self.head
    pre=self.head
    #for case having more than 2 nodes
    while(temp.next):
        pre=temp
        temp=temp.next
    self.tail=pre
    self.tail.next=None
    self.length=-1
    if self.length==0: #if the list had just one value , we will decrement the length and then set head and tail to None
        self.head=None
        self.tail=None  
    return temp

좋은 웹페이지 즐겨찾기