This is the second day of my participation in the August Text Challenge.More challenges in August

Chain storage structure

• The location of nodes in memory is arbitrary, that is, data elements that are logically adjacent are not necessarily physically adjacent

The term

• Node: Storage image of data element. It consists of two parts: data domain and pointer domain
  • Data domain: Stores element numeric data
  • Pointer field: Storage location for immediate successors
• Linked list: N nodes form a linked list of pointer chains. It is a chain storage image of a linear list, called the chain storage structure of a linear list
  • Singly linked lists
    • A list whose node has only one pointer field is called a single or linear list
  • Double linked list
    • A linked list with two pointer fields is called a double-linked list
  • Circular linked list
    • A list that ends end to end is called a circular list
• The head pointer
  • A pointer to the first node in the list
• Finally, some first
  • The node in the linked list where the first data element A1 is stored
• The first node
  • A node appended to the first node of a linked list; Only information such as table flags and table lengths is empty in the data field
  • The benefits of setting headers
    • Easy to handle the initial node
      • The address of the head node is stored in the pointer field of the head node, so the operation at the first position in the linked list is the same as the other positions, without special processing;
    • Facilitate the unified processing of empty tables and non-empty tables
      • The head pointer is a non-null pointer to the head node, regardless of whether the linked list is empty or not, so the treatment of empty and non-empty tables is uniform.

Characteristics of linked lists

• The location of nodes in memory is arbitrary, that is, data elements that are logically adjacent are not necessarily physically adjacent
• Only the head pointer can be used to enter the linked list and scan the rest of the nodes backwards through the pointer field of each node, so the time to find the first node and the last node is not equal

The pros and cons of linked lists

• advantages
  • The number of data elements can be expanded freely
  • Insert and delete operations do not need to move data but only need to modify link Pointers, which is efficient
• disadvantages
  • Low storage density
  • Access efficiency is not high, must use sequential access, that is, when accessing data elements, can only be accessed in the order of the linked list (follow the steps)

Comparison of sequential and linked lists

C++ code implementation

#include<iostream>
#include<stdlib.h>
using namespace std;

#define OVERFLOW -2
#define OK 1
#define ERROR -1

typedef int Status;
typedef int Elemtype;

/* typedef struct LNode{ Elemtype data; struct LNode *next; }LNode; typedef struct{ lnode *l; }LinkList; * /

typedef struct LNode {
	Elemtype data;
	struct LNode* next;
}LNode, * LinkList;


// Construct an empty singly linked list
Status InitList(LinkList& L)
{
	L = new LNode; // The header pointer L points to the header
	if(! L)exit(OVERFLOW);
	L->next = NULL;  // The pointer field is null
	return OK;
}

// Create a singly linked list
void CreateList_H(LinkList& L, int n)
{
	LinkList p;
	int i;
	L = new LNode;  
	L->next = NULL;  // create an empty list of leading nodes
	// for(i = 0; i < n; ++i)
	for (i = 1; i < n + 1; ++i)
	{
		cout << "Please enter no" << i << "Data for each node." << endl;
		p = new LNode;  // generate a new node *p
		cin >> p->data;  // The input element is assigned to the data field of the new node *p
		p->next = L->next;
		L->next = p; // insert the new node *p after the first node}}// Create a singly linked list
Status CreateList_L(LinkList& L, int n)
{
	LinkList r, p;
	int i;
	L = new LNode;
	L->next = NULL;
	// The end points to the head
	r = L;
	for (i = 1; i < n + 1; ++i)
	{
		cout << "Please enter no" << i << "Data for each node." << endl;
		p = new LNode;  // Create a new node
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}
	return OK;
}

/ / value
Status GetElem(LinkList L, int i, Elemtype& e)
{
	// Get the value of the element according to the ordinal I, return the value with e
	int j;
	LinkList p;
	for (p = L->next, j = 1; j < i && p; j++)
		p = p->next;
	if(! p || j > i)return ERROR;
	e = p->data;
	return OK;
}

// Find the location of the element with value e in the list and return its address
LinkList LocateElem_L(LinkList L, Elemtype e)
{
	LinkList p;
	p = L->next;
	while(p && p->data ! = e) { p = p->next; }return p;
}

/ / insert
Status ListInsert(LinkList& L, int i, Elemtype& e)
{
	LinkList p, s;
	int j;
	for (p = L, j = 0; j < i -1 && p; j++)
		p = p->next;
	if(! p || j > i)return ERROR;
	s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

/ / delete
Status ListDelete(LinkList& L, int i, Elemtype& e)
{
	LinkList p, q;
	int j;
	for (p = L, j = 0; j < i -1 && p; j++)
		p = p->next; 
	if(! p || j > i)return ERROR;
	q = p->next;
	p->next = q->next;
	e = q->data;
	delete q;
	return OK;
}

/ / destroy
Status DestroyList(LinkList& L)
{
	LinkList p;
	while (L)
	{
		p = L;
		L = L->next;
		delete p;
	}
	return OK;
}

/ / to empty
Status ClearList(LinkList& L)
{
	LinkList p, q;
	p = L->next; P points to the first node
	while (p)  // Not at the end of the table
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;  // The header pointer field is null
	return OK;
}

/ / o long table
int ListLength_L(LinkList L){
	// Return the number of data elements in L
	int i;
	LinkList p;
	p = L->next;  P points to the first node
	i = 0;
	while (p)  // Count nodes through the list
	{
		i++;
		p = p->next;
	}
	return i;
}

// Check whether the table is empty
int ListEmpty(LinkList L) {
	// If L is empty, return 1; Otherwise, 0 is returned
	if (L->next)
		return 0;
	else
		return 1;
}

int main(a)
{
	LinkList L;
	Elemtype e;
	int i, n;

	// Create a linked list test
	cout << "Please enter table length:";
	cin >> n;
	// create a tail insert
	CreateList_L(L, n);

	cout << "Watch length:";
	cout << ListLength_L(L) << endl;

	// Find tests
	cout << "Please enter the location of the element you want to find:";
	cin >> i;
	GetElem(L, i, e);
	cout << e;

	// Delete the test
	cout << "Please enter the location of the element you want to delete:";
	cin >> i;
	ListDelete(L, i, e);
	cout << e;

	return 0;
}
Copy the code

Python code implementation

• SingleNode

  #! /usr/bin/env python
  # -*- coding: utf-8 -*-
  # @Date : 2019-10-02 09:32:38
  # @Author : Your Name ([email protected])
  # @Link : http://example.org
  # @Version : $Id$
  
  class SingleNode(object) :
  	def __init__(self, item) :
  		self.item = item
  		self.next = None
  
  class SingleLinkList(object) :
  	def __init__(self) :
  		self._head = None
  
  	def isEmpty(self) :
  		return self._head == None
  
  	def length(self) :
  		cur = self._head
  
  		count = 0
  
  		while cur:
  			count += 1
  			cur = cur.next
  
  		return count
  
  	def travel(self) :
  		cur = self._head
  
  		while cur:
  			print(cur.item, end="")
  			cur = cur.next
  		print(a)return None
  
  	def addFirst(self, item) :
  		node = SingleNode(item)
  		node.next = self._head
  		self._head = node
  
  	def append(self, item) :
  		node = SingleNode(item)
  		
  		if self.isEmpty():
  			self._head = node
  
  		else:
  			cur = self._head
  			while cur.next:
  				cur = cur.next
  			cur.next = node
  
  	def insert(self, pos, item) :
  		if pos <= 0:
  			self.addFirst(item)
  		elif pos > (self.length() - 1):
  			self.append(item)
  		else:
  			node = SingleNode(item)
  			count = 0
  			pre = self._head
  			Data starts at 0
  			# 1 should be pos-2
  			while count < (pos - 1):
  				count += 1
  				pre = pre.next
  
  			node.next = pre.next
  			pre.next = node
  
  	def remove(self, item) :
  		cur = self._head
  		pre = None
  
  		while cur:
  			if cur.item == item:
  				if not pre:
  					self._head = cur.next
  				else:
  					pre.next = cur.next
  
  				break
  
  			else:
  				pre = cur
  				cur = cur.next
  
  	def search(self, item) :
  		cur = self._head
  		while cur:
  			if cur.item == item:
  				return True
  			cur = cur.next
  		return False
  
  
  if __name__ == '__main__':
  	sll = SingleLinkList()
  	sll.addFirst(10)
  	sll.addFirst(20)
  	sll.append(30)
  	sll.travel()
  	sll.remove(10)
  	sll.travel()
  	print(sll.search(30))
  	print(sll.search(10))
  	sll.insert(2.40)
  	sll.travel()
  	print(sll.length())
  	print(sll.isEmpty())
  	sll.insert(2.50)
  	sll.travel()
  Copy the code

    20 10 30 
    20 30 
    True
    False
    20 30 40 
    3
    False
    20 30 50 40 
    [Finished in 0.6s]
  Copy the code

• SingleCycLinkedList

  #! /usr/bin/env python
  # -*- coding: utf-8 -*-
  # @Date : 2019-10-02 11:13:14
  # @Author : Your Name ([email protected])
  # @Link : http://example.org
  # @Version : $Id$
  
  class SingleNode(object) :
  	def __init__(self, item) :
  		self.item = item
  		self._head = None
  
  class SingleCysLinkedList(object) :
  	def __init__(self) :
  		self._head = None
  
  	def is_empty(self) :
  		return self._head == None
  
  	def length(self) :
  		if self.is_empty():
  			return 0
  		count = 1
  		cur = self._head
  		while cur.next! = self._head: count +=1
  			cur = cur.next
  		return count
  
  	def travel(self) :
  		if self.is_empty():
  			return
  		cur = self._head
  		print(cur.item, end="")
  
  		while cur.next! = self._head: cur = cur.next
  			print(cur.item, end="")
  		print(a)def addFirst(self, item) :
  		node = SingleNode(item)
  		if self.is_empty():
  			self._head = node
  			node.next = self._head
  		else:
  			node.next = self._head
  			cur = self._head
  			while cur.next! = self._head: cur = cur.next
  			cur.next = node
  			self._head = node
  
  	def append(self, item) :
  		node = SingleNode(item)
  		if self.is_empty():
  			self._head = node
  			node.next = self._head
  		else:
  			node.next = self._head
  			cur = self._head
  			while cur.next! = self._head: cur = cur.next
  			cur.next = node
  			node.next = self._head
  
  	def insert(self, pos, item) :
  		if pos<= 0:
  			self.addFirst(item)
  		elif pos > (self.length() - 1):
  			self.append(item)
  		else:
  			node = SingleNode(item)
  			cur = self._head
  			count = 0
  			while count < (pos - 1):
  				count += 1
  				cur = cur.next
  			node.next = cur.next
  			cur.next = node
  
  	def remove(self, item) :
  		if self.is_empty():
  			return
  		cur = self._head
  		pre = None
  		if cur.item == item:
  			Delete the first element
  			if cur.next! = self._head:while cur.next! = self._head: cur = cur.next
  				cur.next = self._head.next
  				self._head = self._head.next
  			else:
  				There is only one element
  				self._head = None
  
  		else:
  			pre = self._head
  			while cur.next! = self._head:if cur.item == item:
  					pre.next = cur.next
  					return
  				else:
  					pre = cur
  					cur = cur.next
  			if cur.item == item:
  				pre.next = cur.next
  
  	def search(self, item) :
  		if self.is_empty():
  			return False
  		cur = self._head
  		if cur.item == item:
  			return True
  		while cur.next! = self._head: cur = cur.next
  			if cur.item == item:
  				return True
  		return False	
  
  if __name__ == '__main__':
  	ll = SingleCysLinkedList()
  	ll.addFirst(1)
  	ll.addFirst(2)
  	ll.append(3)
  	ll.insert(2.4)
  	ll.insert(4.5)
  	ll.insert(0.6)
  	print("length: {0}".format(ll.length()))
  	ll.travel()
  	print(ll.search(3))
  	print(ll.search(7))
  	ll.remove(1)
  	print("length:", ll.length())
  	ll.travel()
  
  Copy the code

  Length: 6 6 2 1 4 3 5 True False length: 5 6 2 4 3 5 [Finished in 0.4s]Copy the code

• DLinkList

  #! /usr/bin/env python
  # -*- coding: utf-8 -*-
  # @Date : 2019-10-02 12:10:18
  # @Author : Your Name ([email protected])
  # @Link : http://example.org
  # @Version : $Id$
  
  class Node(object) :
  	def __init__(self, item) :
  		self.item = item
  		self.next = None
  		self.prev = None
  
  class DLinkList(object) :
  	def __init__(self) :
  		self._head = None
  
  	def is_empty(self) :
  		return self._head == None
  
  	def length(self) :
  		cur = self._head
  		count = 0
  		while cur:
  			count += 1
  			cur = cur.next
  		return count
  
  	def travel(self) :
  		cur = self._head
  		while cur:
  			print(cur.item, end="")
  			cur = cur.next
  		print(a)def add(self, item) :
  		node = Node(item)
  		if self.is_empty():
  			self._head = node
  		else:
  			node.next = self._head
  			self._head.prev = node
  			self._head = node
  
  	def append(self, item) :
  		node = Node(item)
  		if self.is_empty():
  			self._head = node
  		else:
  			cur = self._head
  			while cur.next:
  				cur = cur.next
  			cur.next = node
  			node.prev = cur
  
  	def search(self, item) :
  		cur = self._head
  		while cur:
  			if cur.item == item:
  				return True
  			cur = cur.next
  		return False
  
  	def insert(self, pos, item) :
  		if pos <= 0:
  			self.add(item)
  		elif pos > (self.length() - 1):
  			self.append(item)
  		else:
  			node = Node(item)
  			cur = self._head
  			count = 0
  			Move to the position preceding the specified position
  			while count < (pos - 1):
  				count += 1
  				cur = cur.next
  			# Change node prev to cur
  			node.prev = cur
  			# point node next to cur
  			node.next = cur.next
  			Cur = prev (cur)
  			cur.next.prev = node
  			Point cur next to node
  			cur.next = node
  
  	def remove(self, item) :
  		if self.is_empty():
  			return
  		else:
  			cur = self._head
  			if cur.item == item:
  				if cur.next= =None:
  					self._head = None
  			else:
  				cur.next.prev = None
  				self._head = cur.next
  			return
  
  		while cur:
  			if cur.item == itme:
  				cur.prev.next = cur.next
  				cur.next.prev = cur.prev
  				break
  
  			cur = cur.next
  
  if __name__ == '__main__':
  	ll = DLinkList()
  	ll.add(1)
  	ll.add(2)
  	ll.append(3)
  	ll.insert(2.4)
  	ll.insert(4.5)
  	ll.insert(0.6)
  	print("length:", ll.length())
  	ll.travel()
  	print(ll.search(3))
  	print(ll.search(4))
  	ll.remove(1)
  	print("length: {}".format(ll.length()))
  	ll.travel()
  Copy the code

  Length: 6 6 2 1 4 3 5 True True length: 5 2 1 4 3 5 [Finished in 0.1s]Copy the code