# The idea and implementation of linked list (Python)

#### 1. The concept of linked list

​ The structure of the linked list is like the chain seen in daily life , It's a ring over ring structure . In the linked list of data structure , Each ring consists of “ Data fields ” and “ Pointer to the domain ” Two parts make up . The specific structure is shown in the following figure ：

​ As shown in the figure, it is the structure of the linked list , Data fields The user stores the element information of the current node , Pointer to the domain Used to link the next node , It should be noted that the linked list is out of order , That is, we just need to maintain the relative position between the elements , There is no need to maintain this location information in a continuous memory space .

#### 2. Creation of linked list

​ The creation of linked list is the same as its principle , We need to initialize each node , Nodes contain data fields data And pointer fields next, After having nodes, we also need to formulate the pointing function of nodes so that nodes can be linked , The specific implementation method is as follows ：

``````class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
# Gets the value of the node
def getData(self):
return self.data
# Get the next node address
def getNext(self):
return self.next
# Set the value of the node
def setData(self, newData):
self.data = newData
# Set node pointing
def setNext(self, newnext):
self.next = newnext
``````

​ The test results are as follows ：

``````# Set the data field of the node
temp1 = Node(93)
temp2 = Node(94)
temp3 = Node(95)
# Set the position pointed by the node pointer
temp1.next = temp2
temp2.next = temp3
temp1.setNext(temp3)
# Get the value of the node
temp2.getNext().getData()
# Output
95
``````

#### 3. The realization of linked list function

​ For a linked list , In addition to creating linked lists , We also need to create a class to realize the function of linked list .

• length： Realize the calculation of the length of the linked list ;
• search： Realize the search of elements in the linked list ;
• remove： Realize the removal of elements in the linked list .

​ The specific implementation is as follows ：

``````class UnorderedList:
# No elements build an empty list
def __init__(self):
# Determine whether the list is empty
def isEmpty(self):
temp = Node(item)
print(" The linked list is empty ！")
while p != None:
print(p.getData(), end="->")
p = p.getNext()
# The length of the list
def length(self):
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
# Look for the element
def search(self, item):
found = False
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
# Remove elements
def remove(self, item):
previous = None
found = False
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
else:
previous.setNext(current.getNext())
``````

​ The test results are as follows ：

``````# Set the data field of the node
temp1 = Node(93)
temp2 = Node(94)
temp3 = Node(95)
# Set the position pointed by the node pointer
temp1.next = temp2
temp2.next = temp3
# Print the length of the linked list
# Output
4
``````

​ Use a loop to construct a linked list ：

``````link_list = UnorderedList()
for i in range(5):