The concept of linked lists
(2) Head pointer: As shown in the figure above, the storage location of the first node in the linked list is called head pointer.
(3) Header node: The header node is the node placed before the first element node. The header node is not a necessary element in the linked list, and its data field is generally meaningless (in some cases, it stores the length of the linked list or is used as a sentinel, etc.). The header node in this paper stores the length of the linked list. With a header, inserting and deleting the first element before the first element is done in the same way as with other nodes.
(4) Head node: is the node of the first element, which is the first node after the head node.
The basic operation of a single linked list
(1) Initialization: Add a header to the list.
(2) Invert linked list: Invert all elements of a single linked list.
(3) List traversal: Print out the length of the list and print all elements in order.
(4) Search: get the element at the specified position.
(5) Element insertion: Insert elements at the specified position.
(6) Element deletion: Delete the element at the specified position.
(7) Delete the linked list: Delete the linked list.
(8) Head plug method to create a linked list: use head plug method to insert a series of elements, create a linked list.
(9) Tail insert method to create a linked list: use tail insert method to insert a series of elements, create a linked list.
(10) Fast and slow pointer: use the principle of fast and slow pointer method to quickly find the middle node of a linked list of unknown length.
In these operations, list inversion is difficult to some extent. The basic design idea is to delete every element in the old list from the old list and insert it into the new list by head interpolation.
The fast pointer moves twice as fast as the slow pointer, so that when the fast pointer points to the last node, the slow pointer points to the middle node.
Characteristics of chain storage structure of linear list
Store the data elements of a linear table with an arbitrary set of storage cells (the cells can be continuous or discontinuous)
Node
The node consists of two fields
** Data domain ** The domain in which data element information is stored
** Pointer field (NEXT) ** A field that stores the immediate successor storage location. The information stored in a pointer field is called a pointer or chain
Single linked list programming —-C language
In C language, functions and data are separated, and each function needs to consider the data transfer problem of linked lists, which greatly increases the difficulty of programming. (1) The header file linklist.h of the linked list
#ifndef LINKLIST_H
#define LINKLIST_Htypedef int ElemType; typedef struct Node { ElemType data; struct Node *Next; }Node; typedef Node* linklist; Typedef enum Bool {FALSE,TRUE// Enumeration defaults to 0, followed by 1}Bool; Bool InitList(linklist* L); Bool GetElem(linkList L, int I, ElemType* e); Bool ListInsert(linkList * L,int I,ElemType e); Bool ListDelete(linkList * L,int I,ElemType* e); Bool ListDeleteAll(linkList * L); Void traverseList(linkList L); Void CreateListHead(linkList * L,int n); Void CreateListEnd(linkList * L,int n) Void Reverse(linkList * L); Int findMiddle(linkList L, ElemType* e); // Find the middle node, assign the value of the element to e, and return the node number, or 0 if the table is empty#endif // LINKLIST_H
Copy the code(2) linklist source file linklist.c
#include "linklist.h"
#include <stdio.h>
Bool GetElem(linklist L, int i, ElemType* e)
{
linklist p=L;
int j;
for(j=1; j<=i; j++) { p=p->Next;if(p==NULL)
return FALSE;
}
*e=p->data;
return TRUE;
}
Bool ListInsert(linklist* L,int i,ElemType e)
{
linklist p=*L,s;
int j;
for(j=1; j<i; j++) { p=p->Next;if(p==NULL)
return FALSE;
}
s=(linklist)malloc(sizeof(Node));
s->data=e;
s->Next=p->Next;
p->Next=s;
(*L)->data++;
return TRUE;
}
Bool ListDelete(linklist* L,int i,ElemType* e)
{
linklist p=*L,q;
int j;
for(j=1; j<i; j++) { p=p->Next;if(p==NULL)
return FALSE;
}
q=p->Next;
p->Next=q->Next;
(*L)->data--;
*e=q->data;
free(q);
return TRUE;
}
Bool InitList(linklist* L)
{
*L=(linklist)malloc(sizeof(Node));
(*L)->data=0;
(*L)->Next=NULL;
return TRUE;
}
void traverseList(linklist L)
{
linklist p=L;
printf("The total length of the list is: %d \n",p->data);
p=p->Next;
while(p)
{
printf("%d ",p->data);
p=p->Next;
}
printf("\n\n");
// printf("display ok! \n");
}
void CreateListHead(linklist* L,int n)
{
linklist p;
int i;
for(i=0; i<n; i++) { p=(linklist)malloc(sizeof(Node)); p->data=i; //rand()%100+1; p->Next=(*L)->Next; (*L)->Next=p; (*L)->data++; } } void CreateListEnd(linklist* L,int n) { linklist p,end=*L; int i;for(i=0; i<n; i++) { p=(linklist)malloc(sizeof(Node)); p->data=i; //rand()%100+1; p->Next=NULL; end->Next=p; end=p; (*L)->data++; } } Bool ListDeleteAll(linklist* L) { linklist p=*L,q;while(p->Next)
{
q=p->Next;
p->Next=q->Next;
(*L)->data--;
free(q);
}
free(p);
returnTRUE; } void Reverse(linkList * L) {linkList cur, TMP; // Initialize the new header cur=*L; cur=cur->Next; (*L)->Next=NULL; // Note that this sentence cannot be reversed, or else it cannot be moved backwhile(cur) { tmp=cur; cur=cur->Next; TMP ->Next=(*L)->Next; // Insert new header (*L)->Next= TMP; } } int findMiddle(linklist L, ElemType* e) { linklist fast,slow; int i; fast=slow=L;for(i=0; fast! =NULL&&fast->Next! =NULL; fast=fast->Next->Next) { slow=slow->Next; i++; } *e=slow->data;return i;
}
Copy the code(3) Main program main.c
#include <stdio.h>
#include "linklist.h"
int main()
{
ElemType a;
linklist list;
int num;
printf("1. Initialize \n");
InitList(&list);
traverseList(list);
InitList(&list);
printf("2. Create a singly linked list \n");
CreateListEnd(&list,10);
traverseList(list);
ListDeleteAll(&list);
InitList(&list);
printf("3. Create a single linked list \n");
CreateListHead(&list,10);
traverseList(list);
printf(" 4.元素插入\n"); ListInsert (& list, 5, 10); traverseList(list);printf("5. Element deletion \n");
ListDelete(&list,5,&a);
printf("The deleted element is: %d",a);
traverseList(list);
printf(" 6.元素查找\n");
GetElem(list,3,&a);
printf("The third element is: %d \n\n\n",a);
printf("7. Reverse linked list \n");
printf("Original linked list ----------");
traverseList(list);
Reverse(&list);
printf("Inverse linked list ---------");
traverseList(list);
printf("\n\n 8. Fast pointer search intermediate node \n");
printf("Original linked list \n");
traverseList(list);
num=findMiddle(list,&a);
printf("The middle node is %d, which is the %d node \n\n\n",a,num);
ListDeleteAll(&list);
return 0;
}
Copy the code### single list programming implementation —-C++ (1) list class declaration linklist.h
#ifndef LIST_H
#define LIST_Htemplate<typename ElemType>//typedef int ElemType; class List { public: struct Node { ElemType data; struct Node *next; }; List(); // Delete all dynamic nodes ~List(); // Delete all nodes void traverseList(); Bool ListInsert(int I,ElemType d); Void CreateListHead(int n); void CreateListHead(int n); // Insert void CreateListEnd(int n); // Insert void Reverse(); Bool ListDelete(int I,ElemType& e); Bool GetElem(int I,ElemType& e); // Get the element at the ith node position and return e int findMiddle(ElemType& e); Private: Node *head; private: Node *head; private: Node *head; };#endif // LIST_H
Copy the code(2) The implementation of linkList.cpp
#include "linklist.h"
#include<iostream>using namespace std; Template <typename ElemType> List<ElemType>::List()// Initialize {head=new Node; head->next=NULL; head->data=0; } template<typename ElemType> List<ElemType>::~List() {Node* del;while(head->next! =NULL) { del=head; head=head->next; delete del; } delete head; } template<typename ElemType> void List<ElemType>::traverseList() {Node *ph=head; cout<<"The total length of the list is:<<head->data<<endl;
ph=ph->next;
for(; ph! =NULL; ph=ph->next) cout<<ph->data<<""; cout<<endl; } template<typename ElemType> void List<ElemType>::CreateListHead(int n)// head->NULL; //head->p1->NULL; //head->p2->p1->NULL; {for(int i=0; i<n; i++) { Node* cur=new Node; cur->data=i; cur->next=head->next; head->next=cur; head->data++; } } template<typename ElemType> bool List<ElemType>::ListInsert(int i,ElemType d) { Node *p=head,*cur;for(int j=1; j<i; j++) { p=p->next;if(p==NULL)
return false;
}
cur=new Node;
cur->data=d;
cur->next=p->next;
p->next=cur;
head->data++;
return true; } template<typename ElemType> void List<ElemType>::CreateListEnd(int n); //head->p1->NULL; //head->p1->p2->NULL; { Node* cur,*end; end=head;for(int i=0; i<n; i++) { cur=new Node; cur->data=i; cur->next=end->next; end->next=cur; end=cur; head->data++; } } template<typename ElemType> bool List<ElemType>::ListDelete(int i,ElemType& e) { Node *p=head,*cur;for(int j=1; j<i; j++) { p=p->next;if(p==NULL)
return false; } cur=p->next; E =cur->data; p->next=cur->next; // assign the next node to the previous node head->data--; delete cur;return true;
}
template<typename ElemType>
bool List<ElemType>::GetElem(int i,ElemType& e)
{
Node* p=head;
for(int j=0; j<i; j++) { p=p->next;if(p==NULL)
return false;
}
e=p->data;
return true; } /* * this program is the original version of the program, the idea of this program is clearer, the following program is improved, the code is more concise. Void List<ElemType>::Reverse() {Node* cur=head; // Node* newhead,* TMP; // initialize the new header newhead=head; cur=cur->next; Newhead ->next=NULL; // Note that this sentence cannot be reversed, or else it cannot be moved backwhile(cur) { tmp=cur; cur=cur->next; TMP ->next=newhead->next; Newhead ->next= TMP; } head= newhead; // This step is redundant, because the new and old head point to the same location. In fact, newhead is a redundant variable. } */ template<typename ElemType> void List<ElemType>::Reverse() {Node* cur,* TMP; // initialize the new header cur=head; cur=cur->next; Head ->next=NULL; // Note that this sentence cannot be reversed, or else it cannot be moved backwhile(cur) { tmp=cur; cur=cur->next; TMP ->next=head->next; Head ->next= TMP; } } template<typename ElemType> int List<ElemType>::findMiddle(ElemType& e) { Node *fast,*slow; int i; fast=slow=head;for(i=0; fast! =NULL&&fast->next! =NULL; fast=fast->next->next) { slow=slow->next; i++; } e=slow->data;return i;
}
Copy the code(3) The main program main.cpp
#include <iostream>
#include"linklist.cpp"
using namespace std;
int main()
{
List<int> list;
bool success;
cout<<"1. Initialization"<<endl;
list.traverseList();
List<int> list1;
list1.CreateListEnd(10);
cout<<endl<<endl<<"2. Create a single linked list by tail Insertion"<<endl;
list1.traverseList();
List<int> list2;
cout<<endl<<endl<<"3. Create a single linked list using head insertion"<<endl;
list2.CreateListHead(10);
list2.traverseList();
cout<<endl<<endl<<"4. Element Insertion"<<endl; List2. ListInsert (5, 10); list2.traverseList(); cout<<endl<<endl<<" 5.元素删除"<<endl;
int a;
list2.ListDelete(5,a);
cout<<"The deleted element is:"<<a<<"";
list2.traverseList();
cout<<endl<<endl<<"6. Element Lookup"<<endl;
list2.traverseList();
success=list2.GetElem(3,a);
if(! success) cout<<"error"<<endl;
else
cout<<"The element being searched is:"<<a<<endl;
cout<<endl<<endl<<"7. Reverse linked lists"<<endl;
cout<<"Original linked list"<<endl;
list2.traverseList();
list2.Reverse();
cout<<endl<<"Inverse linked list"<<endl;
list2.traverseList();
cout<<endl<<endl<<"8. Fast and slow Pointers to find intermediate nodes"<<endl;
int num;
cout<<"Original linked list"<<endl;
list2.traverseList();
num=list2.findMiddle(a);
cout<<"The middle node is"<<a<<"This is number one on the list."<<num<<"A node"<<endl<<endl<<endl;
return 0;
}
Copy the code### Run result
