Graphical algorithms and data structures

1, the preface

We’re going to start today with linked lists, single linked lists in this lecture, and double linked lists in the next lecture.

Take a look below!!

2, code,

Template:

// C++
#include <iostream>
using namespace std;

//C++ unidirectional linked list template
class MyListForward{
private:
	struct ListNode{
		int val;
		ListNode *next;
		ListNode(int x) :val(x), next(nullptr){}
	};
	ListNode* head;
public:
	MyListForward() :head(nullptr) {}// Get the value of the index node in the list
	int get(int index){
		int i = 0;
		ListNode *p = head;
		while (p&&i<index){
			p = p->next;
			i++;
		}
		if (p)return p->val;
		else return - 1;
	}

	// Insert a node with the value val in the head of the list
	void addAtHead(int val){
		ListNode *p = new ListNode(val);
		p->next = head;
		head = p;// Replace the head node
	}

	// Add a node with the value val to the end of the list
	void addAtTail(int val){
		ListNode *p = new ListNode(val);
		// If the list is empty, use the new node as the head node
		if (head == nullptr){
			head = p;
			return;
		}
		ListNode *q = head;
		// Iterate until q's next node is empty
		while (q->next){
			q = q->next;
		}
		q->next = p;
	}

	// Add a node with the value val before the node with index
	void addAtIndex(int index, int val){
		ListNode *node = new ListNode(val);
		// if index is less than or equal to 0, insert a node in the header
		if (index <= 0) {// If index is less than or equal to 0, we just need to insert a new node before the head node
			// Note that the pointer p cannot be used here,
			// When p=node, the address pointed to by p is changed, and the address pointed by head is not changed.
			// So we use the pointer head here
			node->next = head;
			head = node;
			return;
		}
		int i = 0;
		ListNode *p = head;
		// Insert a new node before the index of the node, we need to find its precursor,
		// Then insert it after its precursor node
		while (p&&i<index - 1){
			p = p->next;
			++i;
		}
		//2. P is the precursor node of the index node
		if(p){ node->next = p->next; p->next = node; }}// Delete the node whose index is index
	void deleteAtIndex(int index){
		// if index = 0, delete head
		if (index == 0&& head ! =nullptr){
			ListNode *del = head;
			head = head->next;
			delete del;
			return;
		}
		int i = 0;
		ListNode* p = head;
		// Delete the node whose index is index, we need to find its precursor p,
		//p->next indicates that the node needs to be deleted
		while (p&&i<index - 1){
			p = p->next;
			i++;
		}
		// index exceeds the range of the linked list and fails to be deleted
		if(! p)return;
		// select * from p->next
		if (p->next){
			ListNode *del = p->next;
			p->next = del->next;
			deletedel; }}};Copy the code

3, the body

Each node in a singly linked list contains not only values, but also reference fields linked to the next node. In this way, a singly linked list organizes all the nodes in order.

Initialize your singly linked list first:

val
next

If you want to add a new value after a given node, there are three cases:

• Head node;
  

  

• End node;
  

  

• Any position;
  

  

Unlike arrays, you do not need to move all elements after the inserted element. Therefore, new nodes can be inserted into the linked list in O(1) time complexity, which is very efficient.

If you want to remove an existing node from a single linked list, there are two cases:

• Head node;
  

  

• Any position;
  

  

  The time to delete a node will be O(N). The space complexity is O(1) because only constant space is needed to store Pointers.

  

4, the instance,

LeetCode 707, a problem for designing linked lists.

/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList* obj = new MyLinkedList(); * int param_1 = obj->get(index); * obj->addAtHead(val); * obj->addAtTail(val); * obj->addAtIndex(index,val); * obj->deleteAtIndex(index); * /
Copy the code

If lucky enough to help you, please help me a [praise], to a [attention]! I would appreciate an encouragement along the way.

If you want more resources, please follow @I’m Guan Xiaoliang, MAX~