Pre question

Q1 structure is required to implement single linked list in C language. How to implement it in python?
Q2 what is the difference between process oriented and object-oriented implementation of a single linked list?

Learning content

1. Define single linked list
2. Implementation of single linked list
3. Method of single linked list
4. Difference between single linked list and sequential list

Sudden questions during learning

Why define two classes Node and a SingleList when implementing linked lists in Q3 python
Q4 current and current What does next stand for?
When will Q5 use current? When to use current next?

Learning output

1. Define single linked list

1. A single linked list is a linear list. A single linked list is composed of one node. Each node has two fields, one data field and one pointer field.
2. The "chain" representation is one after another. How to realize this representation, the pointer field of the previous node stores the address of the next node. Who is in front of who is the precursor and who is behind who is the successor. There is no precursor in the head node and no successor in the tail node.

2. Implementation of single linked list

A1

1. Representation of nodes
   C language is used for process oriented representation, and typedef + struct can be used to represent a node as follows:

typedef struct node
{
	ElemType data;
	struct node *next;
}Node, *LinkList;

But just finished learning python, how to implement this node? Use the class to create one

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

1. Representation of linked list

The following method is used in C language to represent the creation of a linked list L

LinkList L = (LinkList)malloc(sizeof(Node));
L->next = NULL

class SingleList:

    """Implement single linked list"""
    def __init__(self, node=None):
        self._head = node

my_list = SingleList()

The picture is generated by python Tutor

A3
Why create two classes? Because the final operation is to use only the linked list object to operate the nodes inside. The node is an object and needs a class. The linked list is also an object and needs a class.

3. General operation of single linked list

1. is_empty

'''Determine whether the linked list is empty'''

    def is_empty(self):
        return self._head is None

1. length

    def length(self):
        current = self._head
        count = 0
        while current is not None:
            count += 1
            current = current.next

        return count

1. travel

'''Traversal linked list'''
    def travel(self):
        current = self._head
        while current is not None:
            print("{0}".format(current.data), end=" ")
            current = current.next
        print(" ")

1. add

'''Insert a node at the head of the linked list'''
    def add(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            node.next = self._head
            self._head = node

1. append

'''Insert elements at the end of the linked list'''
    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            current = self._head
            while current.next is not None:
                current = current.next
            current.next = node

6.insert

'''
        Insert a linked list at a location
        Two special positions
        1,At position 0 add
        2,In the last position append
        
        When inserting a node, you need to consider the previous node in the current position.
    '''
    def insert(self, item, pos):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = Node(item)
            pre = self._head
            count = 0
            while count < (pos - 1):
                pre = pre.next
                count += 1
            node.next = pre.next
            pre.next = node

1. remove

'''
        Delete node
        Note: what if the deleted node is the first one?
    '''
    def remove(self, item):
        current = self._head
        if self.is_empty():
            return
        elif current.data == item:
            self._head = current.next
        else:
            previous = None
            while current is not None and current.data != item:
                previous = current
                current = current.next

            previous.next = current.next

1. search

    '''Find nodes in the linked list'''
    def search(self, item):
        found = False
        if self.is_empty():
            return found
        else:
            current = self._head
            while current is not None and not found:
                if current.data == item:
                    found = True
                else:
                    current = current.next
        return found

8. Realize the above operation

if __name__ == "__main__":
    my_list = SingleList()

    print("add Operation:")
    my_list.add(98)
    my_list.add(99)
    my_list.travel()
    print("{:#^50}".format(""))

    print("append Operation:")
    my_list.append(100)
    my_list.append(101)
    my_list.append(102)
    my_list.append(103)
    my_list.travel()
    print("{:#^50}".format(""))

    print("insert Operation:")
    my_list.insert(99, 0)
    my_list.insert(104, 10)
    my_list.insert(19, 3)
    my_list.insert(56, 5)
    my_list.travel()
    print("{:#^50}".format(""))

    print("remove Operation:")
    my_list.remove(19)
    my_list.remove(56)
    my_list.travel()
    print("{:#^50}".format(""))

    print("search Operation:")
    print(my_list.search(1000))
    print(my_list.search(101))

    print("The length of the linked list is:{0}".format(my_list.length()))

4. The difference between linked list and sequential list

operation	Linked list time	Sequence table time
Insert element add into header	O(1)	O(n)
Insert element append at the end of the table	O(n)	O(1)
Insert element insert anywhere	O(n)	O(n)
Access element	O(n)	O(1)

5. About current and current The difference between next

A4 and A5
Current refers to the current entire node, while current Next refers to the address of the next node

The picture is generated by python Tutor

Use two functions to test current and current Next makes the while loop termination condition. How many times does count traverse? I guess current is better than current The next count needs to be repeated.

    def traverse_next(self):
        current = self._head
        count = 0;
        if self.is_empty():
            return count
        else:
            while current.next is not None:
                count += 1
                current = current.next
        return count

    def traverse(self):
        current = self._head
        count = 0
        if self.is_empty():
            return count
        else:
            while current is not None:
                count += 1
                current = current.next
        return count

As I guessed, current - > 7, current next —> 6

Modify the above code as follows, plus a return current data. What will happen?

    def traverse_next(self):
        current = self._head
        count = 0;
        if self.is_empty():
            return count
        else:
            while current.next is not None:
                count += 1
                current = current.next
        return count,current.data

    def traverse(self):
        current = self._head
        count = 0
        if self.is_empty():
            return count
        else:
            while current is not None:
                count += 1
                current = current.next
        return count, current.data

The code results show that although current and current Next can be the traversal condition, but current Next can return the value field of the tail node, and current will traverse the whole node. Finally, current = None. When current. Is called Data will naturally report an error.

Use append() to add elements at the end of the table and traverse the single linked list to explain when to use current and when to use current next

 '''Insert elements at the end of the linked list'''
    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            current = self._head
            while current.next is not None:
                current = current.next
            current.next = node

    def append2(self,item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            current = self._head
            previous = None
            while current is not None:
                previous = current
                current = current.next
            previous.next = node

	'''Traversal single linked list'''
    def travel(self):
        current = self._head
        while current is not None:
            print("{0}".format(current.data), end=" ")
            current = current.next
        print(" ")
        
    def travel2(self):
        current = self._head
        while current.next is not None:
            print("{0}".format(current.data), end=" ")
            current = current.next
        print(" ")

if __name__ == "__main__":
    my_list = SingleList()

    my_list.append(100)
    my_list.append(101)
    my_list.append(102)
    my_list.append(103)
    my_list.append2(104)

    print("use current When the conditions of the cycle are:")
    my_list.travel()
    print("{:#^50}".format(""))
    print("use current.next When the conditions of the cycle are:")
    my_list.travel2()
    print(my_list.length())

Use current. When adding elements to the footer Next is convenient. Traverse the linked list with current and current Next will omit the last element at the end of the table.

A2
The feeling of a linked list is realized by process oriented C language and object-oriented python:

1. The code has become less. Behind the simplicity is the need to be familiar with the object. Everything in python is an object. Each object has three elements. The id type value variable stores the address. For example, the first node in C is current = L - > next, and current = self in python_ head
2. C language can not be forgotten step by step. It is easier to think about the underlying principles. On the contrary, object-oriented high-level language has simple operation, but it makes people feel stupid.