I understand most of the code, but what I don't understand is what's happening in the append_after function. How exactly are the elements in the linked list being appended after each other? As far as I can see last_node.next is never being instructed to point to the next element. Also it says "While last_node.next is not None" but isn't it None by default? I'm not seeing what would make it not "None" if I didn't specifically code it to do that.
class node:
def __init__(self, data):
self.data = data
self.next = None
class linked_list:
def __init__(self):
self.head = None
def display(self):
node = self.head
while node is not None:
print(node.data)
node = node.next
def append_after(self, data):
new_node = node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head # I'm assuming this starts at the letter "A"?
while last_node.next is not None: # What makes it not None?
last_node = last_node.next
last_node.next = new_node # It comes here after finishing the loop?
ll = linked_list()
ll.append_after("A")
ll.append_after("B")
ll.append_after("C")
ll.append_after("D")
ll.display()
OUTPUT
A
B
C
D
Below is a different way to call the objects. If I call the objects like I do in the example below I can easily understand it because I can clearly see what's being defined as the next element, but I don't understand how the append_after function returns the same result.
ll = linked_list()
ll.head = node("A")
data2 = node("B")
data3 = node("C")
data4 = node("D")
ll.head.next = data2
data2.next = data3
data3.next = data4
ll.display()
I'm using Python 3 and I've already looked at similar questions but they weren't explained very well. Is something happening under the hood that I don't understand?
CodePudding user response：
It may help to visualise the process. When ll = linked_list() is executed, an instance of linked_list is created, its head attribute is set to None and the reference to that instance is assigned to ll. We can picture the state as follows:
ll
↓
┌────────────┐
│ head: None │
└────────────┘
Now ll.append_after("A") is called. During this call self has the reference to the linked list, and with new_node = node("A") the new node is created with its data attribute set to "A" and its next attribute set to None. Let's already picture that state:
self (ll)
↓
┌────────────┐
│ head: None │
└────────────┘
┌────────────┐
│ data: "A" │
│ next: None │
└────────────┘
↑
new_node
Because self.head is None, we get into the if block, where self.head = new_node is executed. This makes the new node instance a member of the list:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐
│ data: "A" │
│ next: None │
└────────────┘
↑
new_node
The append_after function returns, and the main program makes the call ll.append_after("B"). Again a new node is created with new_node = node("B"). This leads to this state:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │
│ next: None │ │ next: None │
└────────────┘ └────────────┘
↑
new_node
This time the if condition (self.head is None) is not true, so we get to last_node = self.head, introducing another name that references the first node in the list:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │
│ next: None │ │ next: None │
└────────────┘ └────────────┘
↑ ↑
last_node new_node
Now the while loop starts, but its condition is false, because last_node.next is None -- which is an indication that it currently is the last node in the list. And that's what we need: we want to have a reference to the last node in the list so we can attach the new node just after it.
After the while loop (which didn't make iterations) we execute last_node.next = new_node. This performs the attachment:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │
│ next: ────────► │ next: None │
└────────────┘ └────────────┘
↑ ↑
last_node new_node
The function returns. Let's do one more call: ll.append_after("C"). Again a new node is created, the if condition is False, and last_node gets again a reference to the first node in the list. So just before the while loop starts we have this state:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │ │ data: "C" │
│ next: ────────► │ next: None │ │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
last_node new_node
This time the while condition is true, which means that last_node is not what its name suggest -- it is not the last node in the list, so an iteration of the loop is executed, with last_node = last_node.next:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │ │ data: "C" │
│ next: ────────► │ next: None │ │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
last_node new_node
Now the while condition is true, which means that last_node is truly the last node of the list. It is here that we need to attach the new node. So after last_node.next = new_node is executed, we get:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │ │ data: "C" │
│ next: ────────► │ next: ────────► │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
last_node new_node
The call ll.append_after("D") will go through the same process: last_node will start again from the left, and via the loop it will reach the last node in the list, and then the new node will be appended there.
I hope this clarifies it.
CodePudding user response：
yes i think its saying when its not default its the new node