链表(linked list)

链表的特点是元素可以存储到内存的任意位置,每个元素都通过指针变量存储下一个元素的地址,从而将元素串接起来形成的,因此每个单元至少有两个域。

一、单链表(single linked list)

一个域用于数据元素的存储,另一个域是指向其他单元的指针。
这里具有一个数据域和多个指针域的存储单元通常称为结点(node)一种最简单的结点结构如图所示,它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素,指针域用于指向下一个具有相同结构的结点。
因为只有一个指针结点,称为单链表。 

single linked list

PPT

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**************************************************************** 
 * Description: C++ implement for single linked list
 * Author: Alex Li
 * Date: 2022-04-18 20:05:00
 * LastEditTime: 2024-04-16 12:26:31
****************************************************************/
#include <iostream>
using namespace std;
int n;
// Definition of the Node structure for the linked list.
struct Node{
    int data;       // Data element of the node
    Node *next;     // Pointer to the next node in the list
};

Node *head = NULL; // Head pointer for the list, initially set to NULL

// Function prototypes for clarity and organization.
void PrintNode();

// Function to add nodes to the linked list.
void AddNode(){
    
    cout << "Please input the count of nodes: ";
    cin >> n;

    Node *newNode = new Node; // Allocate a new node in memory
    head = newNode; // Set the head to the new node
    cout << "Please input the data of node: ";
    int x;

    for (int i = 0; i < n; i++) {
        cin >> x;
        newNode->data = x; // Set the data of the node
        newNode->next = new Node; // Allocate a new node for the next
        newNode = newNode->next;
        newNode->next = NULL; // Set the next of the new node to NULL
    }
    PrintNode(); // Print the linked list
}

// Function to insert a new node at a specified position.
void InsertNode(){
    int position, data;
    cout << "Please give me position and data for insert a node: ";
    cin >> position >> data;
    Node *p = head, *newNode;
    int j = 1;
    
    if(position==0){
        newNode = new Node;
        newNode->data=data;
        newNode->next =p;
        head=newNode;
    }
    else if (position <= n+1){
        while (j <= position - 1){
            p = p->next; // Move to the node before the insert position
            j++;
        }
        newNode = new Node; // Create a new node
        newNode->data = data;
        newNode->next = p->next; // Insert the new node in the list
        p->next = newNode;
        n++;
    } else {
        cout << "You input wrong number" << endl;
    }
    PrintNode(); // Print the updated list
}

// Function to delete a node from the linked list.
void DeleteNode(){
    int delete_position;
    cout << "Please input the position of node that you want delete: ";
    cin >> delete_position;
    Node *delete_node = head, *temp_delete_node;

    if (delete_position == 1){
        head = head->next; // Remove the head node
        delete delete_node; // Free the memory of the old head node
    } else {
        for (int i = 1; i < delete_position - 1; i++) {
            temp_delete_node = delete_node->next; // Move to one node before the delete position
        }
        temp_delete_node = delete_node->next; // Node to be deleted
        delete_node->next = temp_delete_node->next; // Unlink the node from the list
        delete temp_delete_node; // Free the memory of the node
    }

    n--;
    PrintNode(); // Print the updated list
}

// Function to search for a node with a given value in the linked list.
void SearchNode() {
    int search_value;
    cout << "Enter the value to search: ";
    cin >> search_value;

    Node *current = head;
    int position = 1;

    while (current != NULL) {
        if (current->data == search_value) {
            cout << "Value " << search_value << " found at position " << position << endl;
            return; // Exit the function if the value is found
        }
        current = current->next;
        position++;
    }
    cout << "Value " << search_value << " not found in the list." << endl;
}

// Function to print all the nodes in the linked list.
void PrintNode(){
    Node *link = head;
    if (link == NULL){
        cout << "List is empty." << endl;
        return;
    }
    cout << "The data of nodes are: ";
    do {
        cout << link->data << " ";
        link = link->next;
    } while (link->next != NULL);
    cout << endl;
}

int main(){
    AddNode();
    InsertNode();
    DeleteNode();
    SearchNode();
    return 0;
}

二、双向链表(Doubly Linked List )

每个结点有两个指针域和若干数据域,其中一个指针域指向它的前趋结点,另一个指针域指向它的后继结点。它的优点是访问、删除、插入更方便,速度更快,但是以空间换时间。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/******************************************************************************
C++ implement for doubly linked list
date:2023-5-27
author: Alex Li
version: 1.0
*******************************************************************************/
#include <iostream>
using namespace std;

// node creation
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

 struct Node* head = NULL;
// insert node at the front
void insertFront(int data) {
  // allocate memory for newNode
  struct Node* newNode = new Node;

  // assign data to newNode
  newNode->data = data;

  // make newNode as a head
  newNode->next =head;

  // assign null to prev
  newNode->prev = NULL;

  // previous of head (now head is the second node) is newNode
  if (head!= NULL)
    head->prev = newNode;

  // head points to newNode
  head= newNode;
}

// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {
  // check if previous node is null
  if (prev_node == NULL) {
    cout << "previous node cannot be null";
    return;
  }

  // allocate memory for newNode
  struct Node* newNode = new Node;

  // assign data to newNode
  newNode->data = data;

  // set next of newNode to next of prev node
  newNode->next = prev_node->next;

  // set next of prev node to newNode
  prev_node->next = newNode;

  // set prev of newNode to the previous node
  newNode->prev = prev_node;

  // set prev of newNode's next to newNode
  if (newNode->next != NULL)
    newNode->next->prev = newNode;
}

// insert a newNode at the end of the list
void insertEnd(int data) {
  // allocate memory for node
  struct Node* newNode = new Node;

  // assign data to newNode
  newNode->data = data;

  // assign null to next of newNode
  newNode->next = NULL;

  // store the head node temporarily (for later use)
  struct Node* temp = head;

  // if the linked list is empty, make the newNode as head node
  if (head == NULL) {
    newNode->prev = NULL;
    head = newNode;
    return;
  }

  // if the linked list is not empty, traverse to the end of the linked list
  while (temp->next != NULL)
    temp = temp->next;

  // now, the last node of the linked list is temp

  // assign next of the last node (temp) to newNode
  temp->next = newNode;

  // assign prev of newNode to temp
  newNode->prev = temp;
}

// delete a node from the doubly linked list
void deleteNode(struct Node* del_node) {
  // if head or del is null, deletion is not possible
  if (head == NULL || del_node == NULL)
    return;

  // if del_node is the head node, point the head pointer to the next of del_node
  if (head == del_node)
    head = del_node->next;

  // if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
  if (del_node->next != NULL)
    del_node->next->prev = del_node->prev;

  // if del_node is not the first node, point the next of the previous node to the next node of del_node
  if (del_node->prev != NULL)
    del_node->prev->next = del_node->next;

  // free the memory of del_node
  delete del_node;
}

// print the doubly linked list
void displayList() {
  struct Node* last;
   last=head;
  while (last != NULL) {
    cout <<last->data << " ";
    last =last->next;
  }
  if (head == NULL)
    cout << "NULL\n";
    cout<<endl;
}

int main() {
  // initialize an empty node
   insertEnd(5);
  insertFront(1);
  insertFront(6);
  insertEnd(9);

  // insert 11 after head
  insertAfter(head, 11);

  // insert 15 after the seond node
  insertAfter(head->next, 15);

  //displayList();

  // delete the  node
  deleteNode(head->next->next->next->next);

  displayList();
}

三、循环链表(Circular Linked List )

1、单向循环链表(singly circular linked list )的最后一个结点的指针指向头结点。如图:

2、双向循环链表(doubly circular linked list) 它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。如图:

四、静态链表

用数组来表示链表,称为静态链表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
using namespace std;

const int N = 100010;
int n=0;
int h[N], node[N], node_next[N], head, idx;

//对链表初始化
void init(){
    head = -1;
    idx = 0;
}

//将x插入到头节点上
void firstNode(int x){
    node[idx] = x;
    node_next[idx] = head;
    head = idx;
    idx ++;
    n++;
}

//将x插入到下标为k的点的后面
void add(int k, int x){
    node[idx] = x;
    node_next[idx] = node_next[k];
    node_next[k] = idx;
    idx ++;
    n++;
}

//将下标是k的点后面的点个删掉
void remove(int k){
    node_next[k] = node_next[node_next[k]];
    n--;
}

void printNode(){
    int i=0;
    while(n>0){
        cout<<node[i]<<endl;
        i=node_next[i];
        n--;
    }
    
}
int main(){
    int k,option,position,value;
    do{
        cout<<"what operation do you want to perform? select option number."<<endl;
        cout<<"0. exit"<<endl;
        cout<<"1. firstnode"<<endl;
        cout<<"2. input newnode"<<endl;
        cout<<"3. remove"<<endl;
        cout<<"4. print nodelist";
        cin>>option; 
        switch(option)
            { 
                 case 0: break; 
                 case 1: 
                        cout<<"input a first node value"<<endl; 
                        cin>>value; 
                        firstNode(value); 
                        break; 
                 case 2: 
                        cout<<"input a new node's  location (after k)and  value  "<<endl;
                       
                        cin>>k>>value;
                        add(k,value); 
                        break; 
                 case 3:
                        cout<<"input a location of node to delete";
                       
                        cin>>k;
                        remove(k);
                        break; 
                case 4: 
                        printNode();
                        break;
               
                default: 
                        cout<<"enter proper option Number"<<endl; 
        } 
    }while(option!=0); 
    return 0;
}
Scroll to Top