數據結構中單鏈表的實現

一個單鏈表就像一列火車系統,每個轉向架連接到下一個轉向架。一個單鏈表是一個單向鏈表;即。,你只能從頭到尾節點遍歷它。這里有一些關于鏈表的快速的事實。它是用來做一個幻燈片或記事本上一些基本操作如撤銷和重做。

如何實現一個單鏈表嗎?

您可以創建節點使用類或結構的單鏈表。你聯系他們使用下一個指針。

// 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;
}