이중 연결 목록

33091 단어
이것이 단일 연결 리스트와 다른 점입니다.
단일 연결 목록


이중 연결 목록


따라서 Singly Linked List에서 노드를 생성할 때 다음과 같은 결과를 얻었습니다.


우리는 실제로


수업 시간에 다음과 같이 작성했습니다.

B
그러나 이중 연결 목록에는 다음이 있습니다.



이제 이중 연결 목록 클래스를 만들 수 있습니다.

클래스를 호출하는 이중 연결 목록을 만듭니다.


이것은 이중 연결 목록을 만듭니다.



전체 코드:

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

#Creating a doubly Linked List which has a node 7
my_doubly_linked_list = DoublyLinkedList(7)

#Printing the list
my_doubly_linked_list.print_list()



추가
사례 1:
값이 없고 추가할 때



그리고 이것을 이것으로


먼저 head가 None을 가리키는지 확인합니다.


해낼거야




사례 2:


이제 이것을 코딩하여 새 노드를 추가합니다.






따라서 전체 코드는 다음과 같습니다.


총 코드:

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

#A linked list of a node 1
my_doubly_linked_list = DoublyLinkedList(1)
#Appending node 2
my_doubly_linked_list.append(2)

my_doubly_linked_list.print_list()





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


이를 위해 다음이 필요합니다.
우리는 아무것도 반환하지 않기 때문에


사례 2: 값이 2개 이상인 경우


먼저 임시 변수를 생성합니다.


그런 다음 꼬리를 이전 노드로 설정합니다.


그런 다음 마지막 항목에서 중단하기 위해 꼬리의 다음 방향을 없음으로 설정합니다.


마지막 노드에 대해 동일:



사례 3:
값이 1개일 때:


팝하고 머리와 꼬리도 없음으로 설정합니다.



목록은 다음과 같습니다.



따라서 코드는 다음과 같습니다.


또한 다음 형식으로 변경할 수 있습니다.

총 코드:

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        #For 0 items in list
        if self.length == 0:
            return None
        temp = self.tail
        #For 1 items in list
        if self.length == 1:
            self.head = None
            self.tail = None 
        #For more than 1 nodes in list
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

#Creates a list of Node 1 & Node 2

my_doubly_linked_list = DoublyLinkedList(1)
my_doubly_linked_list.append(2)


# (2) Items - Returns  Node 2
print(my_doubly_linked_list.pop())
# (1) Item -  Returns  Node 1
print(my_doubly_linked_list.pop())
# (0) Items - Returns  None
print(my_doubly_linked_list.pop())




앞에 추가
사례: 1
목록에 아무것도 없을 때


따라서 머리와 꼬리를 설정합니다.


사례 2:
값이 1개 이상인 경우:


먼저 다음을 수행합니다.


그 다음에


그 다음에



전체 코드는 다음과 같습니다.

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        # If we have no value in the list
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        #If we have more than 1 values
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

#Doubly list with Node 1 & Node 3
my_doubly_linked_list = DoublyLinkedList(2)
my_doubly_linked_list.append(3)

#Prepending Node 1
my_doubly_linked_list.prepend(1)

my_doubly_linked_list.print_list()


얻다
Singly Linked List의 경우 다음 코드가 적합했습니다.




우리는 이것을 이것으로 바꿀 것입니다



사례 1:
이중 연결 목록 내에 있는 항목을 반환해 보겠습니다. 인덱스 1을 반환하자


인덱스가 상반기인 경우


하반기라면

S
꼬리를 임시로 설정하고 뒤로 반복


우리가 그것을 얻을 때 온도를 반환

따라서 전체 코드는

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        #Checking if the index is in 1st half
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        #Checking if the index is in 2nd half
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp #Will return the node . But for value, use temp.value

#Creating a doubly list of 0,5,9,3
my_doubly_linked_list = DoublyLinkedList(0)
my_doubly_linked_list.append(5)
my_doubly_linked_list.append(9)
my_doubly_linked_list.append(3)


#Lokking for index 1 no node
print(my_doubly_linked_list.get(1))

#Looking for index 2 no node
print(my_doubly_linked_list.get(2))



세트
이 인덱스 1 값을 3에서 4로 설정해 봅시다.




그래서 여기서 인덱스가 범위 내에 있는지 확인하고 그렇다면 값을 변경합니다.


그렇지 않으면 False를 반환합니다.

전체 코드는

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp

    def set_value(self, index, value):
        temp = self.get(index)
        #if the index is within the range
        if temp:
            temp.value = value
            return True
        #if the index is not within range    
        return False

#Doubly linked list of 11,3,23,7  
my_doubly_linked_list = DoublyLinkedList(11)
my_doubly_linked_list.append(3)
my_doubly_linked_list.append(23)
my_doubly_linked_list.append(7)


#setting index value to 4

my_doubly_linked_list.set_value(1,4)

my_doubly_linked_list.print_list()



끼워 넣다

특정 인덱스에서 노드를 삽입할 것입니다.
먼저 인덱스가 범위 내에 있는지 확인합니다.



사례 1:
처음에 추가해야 하는 경우



사례 2:
목록의 마지막에 추가



사례 3:
중간 어딘가에 추가합니다.
우리가 이것을 만들고 싶다고 가정하십시오.

그것에



그래서 1과 2 사이에 노드를 삽입하려고 합니다.
따라서 인덱스 1을 이전으로, 인덱스 2를 이후로 설정합니다.





우리는 이것을 만들 것입니다


이에











따라서 코드는

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp

    def set_value(self, index, value):
        temp = self.get(index)
        if temp:
            temp.value = value
            return True
        return False

    def insert(self, index, value):
        #to check if the index is within range
        if index < 0 or index > self.length:
            return False
        #to add a node at the start
        if index == 0:
            return self.prepend(value)
        #to add a node at the end    
        if index == self.length:
            return self.append(value)
        #to add a node within the list
        new_node = Node(value)
        before = self.get(index - 1)
        after = before.next

        new_node.prev = before
        new_node.next = after
        before.next = new_node
        after.prev = new_node

        self.length += 1   
        return True  


#Doubly linked list of nodes 1 ,3
my_doubly_linked_list = DoublyLinkedList(1)
my_doubly_linked_list.append(3)



#at the index 1, adding node 2
my_doubly_linked_list.insert(1,2)

my_doubly_linked_list.print_list()



제거하다

인덱스가 범위를 벗어났는지 확인


사례 1:
첫 번째 항목을 반환합니다.


이것에 이것


이를 위해 우리는 팝


사례 2:
마지막에서 제거합니다.


사례 3:
중간에서 무언가를 제거하려면


예를 들어 인덱스 2 숫자 값을 제거합니다. 첫째, 변수를 가리 킵니다.




다음과 같을 수 있습니다








사용



총 코드는

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp

    def set_value(self, index, value):
        temp = self.get(index)
        if temp:
            temp.value = value
            return True
        return False

    def insert(self, index, value):
        if index < 0 or index > self.length:
            return False
        if index == 0:
            return self.prepend(value)
        if index == self.length:
            return self.append(value)

        new_node = Node(value)
        before = self.get(index - 1)
        after = before.next

        new_node.prev = before
        new_node.next = after
        before.next = new_node
        after.prev = new_node

        self.length += 1   
        return True  

    def remove(self, index):
        #Checking the range
        if index < 0 or index >= self.length:
            return None
        #to remove from the beginning    
        if index == 0:
            return self.pop_first()
        #to remove from the last    
        if index == self.length - 1:
            return self.pop()

        #to remove from the middle of the doubly linked list
        temp = self.get(index)

        temp.next.prev = temp.prev
        temp.prev.next = temp.next
        temp.next = None
        temp.prev = None

        self.length -= 1
        return temp

# a doubly linked list of 0,1 & 2 nodes
my_doubly_linked_list = DoublyLinkedList(0)
my_doubly_linked_list.append(1)
my_doubly_linked_list.append(2)


# removing index 1 out of the list
print(my_doubly_linked_list.remove(1), '\n')

my_doubly_linked_list.print_list()


완료!

좋은 웹페이지 즐겨찾기