数据结构中单链表的实现

一个单链表就像一列火车系统,每个转向架连接到下一个转向架。一个单链表是一个单向链表;即。,你只能从头到尾节点遍历它。这里有一些关于链表的快速的事实。它是用来做一个幻灯片或记事本上一些基本操作如撤销和重做。

如何实现一个单链表吗?

您可以创建节点使用类或结构的单链表。你联系他们使用下一个指针。

// implementation of singly linked list
#include <bits/stdc++.h>
using namespace std;
//A class to create node
class Node {
public:
int data;
Node* next;
};
// A function to print the given linked list
// starting from the given node
void printList(Node* n)
{
while (n != NULL)
 {
cout << n->data << " ";
n = n->next;
 }
}
int main()
{
//creating nodes
Node* head = NULL;
Node* second = NULL;
Node* third = NULL;
Node* tail = NULL;
// allocate four nodes
head = new Node();
second = new Node();
third = new Node();
  tail = new Node(); 
head->data = 2; // assign data in head node
head->next = second; // Link first node with second
  second->data = 3; // assign data to second node
  second->next = third;//Link second node with third
  third->data = 5; // assign data to third node
  third->next = tail;//Link third node with tail
tail->data = 7;// assign data to tail node
tail->next=NULL;//link tail node with NULL
//printing singly linked list
cout<<"Created singly linked list: "<<endl;
printList(head);
return 0;
}

哪些操作可以执行在一个单链表吗?

你可以在一个单链表执行两个操作:

插入

删除

如何插入一个节点在一个单链表吗?

你可以在三个不同的位置插入一个节点,它们是:

一开始

结束时

在一个特定的位置后一个节点

//A c++ code to insert a node 
//in singly linked list 
#include <bits/stdc++.h>
using namespace std; 
//A class to create nodes
class Node 
{ 
public:
int data; 
Node *next; 
}; 
// A function to insert a node at the 
//beginning of singly linked list
void push(Node** head, int newdata) 
{ 
Node* newnode = new Node();//creating newnode
newnode->data = newdata; //put in data
newnode->next = (*head); //link newnode to head
(*head) = newnode; //changing head
} 
// A function to insert a node after  
//a specific node in a singly linked list
void insertAfter(Node* prevnode, int newdata) 
{ 
//check if previous node is null
if (prevnode == NULL) 
{ 
cout<< “the given previous node cannot be NULL”; 
return; 
} 
Node* newnode = new Node();//creating newnode
newnode->data = newdata; //put in data
//link newnode to prevnode’s next node
newnode->next = prevnode->next; 
prevnode->next = newnode; //link prevnode to newnode
} 
// A function to insert a node at the 
//end of singly linked list
void append(Node** head, int newdata) 
{ 
Node* newnode = new Node();//creating newnode
Node *last = *head; // creating a ‘last’ node
newnode->data = newdata; //put in data
newnode->next = NULL; //link newnode with null
//Check if head is null
if (*head == NULL) 
{ 
*head = newnode; 
return; 
} 
//traversing ‘last’ node to end of the linked list 
while (last->next != NULL) 
last = last->next; 
//link ‘last’ node with newnode
last->next = newnode; 
return; 
} 
// A function to print the given linked list
// starting from the given node
void printList(Node *node) 
{ 
while (node != NULL) 
{ 
cout<<" "<<node->data; 
node = node->next; 
} 
}   
/* Driver code*/
int main() 
{ 
/* Start with the empty list */
Node* head = NULL;       
// Insert 6 at the end,
append(&head, 6); 
//6->NULL     
// Insert 7 as head 
push(&head, 7); 
//7->6->NULL       
// Insert 1 as head. 
push(&head, 1); 
//1->7->6->NULL      
// Insert 4 at the end  
append(&head, 4); 
//1->7->6->4->NULL       
// Insert 8, after 7
insertAfter(head->next, 8); 
//1->7->8->6->4->NULL      
cout<<"Created Linked list is: "; 
printList(head);       
return 0; 
}

如何从一个单链表中删除一个节点?

你可以删除一个节点从3个不同的位置,它们是:

从一开始

从过去的

给定节点后从一个特定的位置

//A c++ code to insert a node 
//in singly linked list
#include <bits/stdc++.h>
using namespace std;
//A class to create node
class Node{
public:
int data;
Node* next;
};
//insert a node at the beginning
void push(Node** head, int newdata)
{
//create newnode
Node* newnode = new Node();
newnode->data = newdata;//put in data
newnode->next = (*head);//link newnode with head
(*head) = newnode;//changing head
}
//A function to delete a node
void deleteNode(Node** head, int key)
{
Node* temp = *head;//creating temp node
Node* prev = NULL;//creating prev node
//checking if node to be deleted is head the node
if (temp != NULL && temp->data == key)
{
*head = temp->next;//changing head
delete temp; //delete node
return;
}
else
{
//traversing to find key to delete
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL)
return;
prev->next = temp->next;
delete temp;//delete node
}
}
// This function prints contents of
// linked list starting from the
// given node
void printList(Node* node)
{
while (node != NULL)
{
cout << node->data << " ";
  node = node->next;
}
}
// Driver code
int main()
{    
// Start with the empty list
Node* head = NULL; 
// Add elements in linked list
push(&head, 7);
push(&head, 1);
push(&head, 3);
push(&head, 2);
puts("Created Linked List: ");
printList(head);
deleteNode(&head, 1);
puts("\nLinked List after Deletion of 1: "); 
printList(head);  
return 0;
}