Démonstration animée de liste statique

链表是一种线性数据结构，用于借助节点存储数据集合。链表由数据和下一个节点的引用两项组成。借助指针给出对下一个节点的引用，数据是节点的值。每个节点都包含数据并链接到其他节点。它是称为节点的数据元素的有序集合，线性顺序由指针维护。它比数组具有优势，因为节点的数量（即链表的大小）不固定，可以根据需要增长和缩小，这与数组不同。链表的一些特点如下：连续的元素通过指针连接。链表的大小不固定。链表的最后一个节点指向null。内存不会浪费，但会消耗额外的内存，因为它还使用指针来跟踪下一个连续节点。链表的入口点称为头。

静态链表的各种类型如下：

单静态链表： 它是最基本的静态链表，其中遍历是单向的，即从头节点到最后一个节点。

例子：

C++
Python
Java
C＃
JavaScript

C++

      
        
            class Node {
public:
    int
                  data;
    Node* next;
 
    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};
 
class SinglyLinkedList {
public:
    Node* head;
 
    SinglyLinkedList() {
        this->head = nullptr;
    }
 
    void add_node(int data) {
        Node* new_node = new Node(data);
        new_node->next = this->head;
        this->head = new_node;
    }
};

          

      
    

Python

      
        
            class Node:
  def __init__(self, data):
    self.data =
                  data
    self.next
                  = None
 
class SinglyLinkedList:
  def __init__(self):
    self.head =
                  None
     
  def add_node(self, data):
    new_node = Node(data)
    new_node.next = self.head
                
    self.head =
                  new_node

          

      
    

Java

      
        
            class Node {
    int
                  data;
    Node next;
 
    Node(int d) {
                
        data = d;
        next = null;
                
    }
}
 
class SinglyLinkedList {
    Node head;
 
    SinglyLinkedList() {
        head = null;
                
    }
 
    void
                  add_node(int data) {
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;
    }
}

          

      
    

C#

      
        
            using System;
 
public class Node {
    public
                  int data;
    public
                  Node next;
 
    public
                  Node(int d) {
        data = d;
        next = null;
                
    }
}
 
public class SinglyLinkedList {
    public
                  Node head;
 
    public
                  SinglyLinkedList() {
        head = null;
                
    }
 
    public
                  void add_node(int data) {
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;
    }
}

          

      
    

Javascript

      
        
            class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
 
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
 
  add_node(data) {
    let new_node = new Node(data);
    new_node.next = this.head;
    this.head = new_node;
  }
}

          

      
    

双向静态链表： 在这种静态链表中，可以通过两种方式进行遍历，因此需要一个额外的指针。

例子：

C

      
        
            #include <stdio.h>
                
#include <stdlib.h>
 
struct Node {
    int
                  data;
    struct Node* next;
    struct Node* prev;
};
 
struct DoublyLinkedList {
    struct Node* head;
};
 
void addNode(struct DoublyLinkedList* list, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = list->head;
    newNode->prev = NULL;
    if
                  (list->head != NULL) {
        list->head->prev = newNode;
    }
    list->head = newNode;
}

          

      
    

C++

      
        
            class Node {
public:
int data;
Node* next;
Node* prev;
Node(int d) : data(d), next(nullptr), prev(nullptr) {}
};
 
class DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
 
void add_node(int data) {
    Node* new_node = new Node(data);
    new_node->next = head;
    if
                  (head != nullptr) {
        head->prev = new_node;
    }
    head = new_node;
}
};

          

      
    

Python

      
        
            class Node:
  def __init__(self, data):
    self.data =
                  data
    self.next
                  = None
    self.prev =
                  None
 
class DoublyLinkedList:
  def __init__(self):
    self.head =
                  None
     
  def add_node(self, data):
    new_node = Node(data)
    new_node.next = self.head
                
    if
                  self.head is not None:
      self.head.prev = new_node
    self.head =
                  new_node

          

      
    

Java

      
        
            public class Node {
    public
                  int data;
    public
                  Node next;
    public
                  Node prev;
     
    public
                  Node(int d) {
        data = d;
        next = null;
                
        prev = null;
                
    }
}
 
public class DoublyLinkedList {
    public
                  Node head;
     
    public
                  DoublyLinkedList() {
        head = null;
                
    }
     
    public
                  void addNode(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        head = newNode;
    }
}

          

      
    

C#

      
        
            public class Node {
    public
                  int data;
    public
                  Node next;
    public
                  Node prev;
     
    public
                  Node(int d) {
        data = d;
        next = null;
                
        prev = null;
                
    }
}
 
public class DoublyLinkedList {
    public
                  Node head;
     
    public
                  DoublyLinkedList() {
        head = null;
                
    }
     
    public
                  void AddNode(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        head = newNode;
    }
}

          

      
    

Javascript

      
        
            class Node {
  constructor(d) {
    this.data = d;
    this.next = null;
    this.prev = null;
  }
}
 
class DoublyLinkedList {
  constructor() {
    this.head = null;
  }
   
                
  addNode(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    if
                  (this.head !== null) {
      this.head.prev = newNode;
    }
    this.head = newNode;
  }
}

          

      
    

循环静态链表： 该静态链表是单向的，但在该列表中，最后一个节点指向第一个节点，即头节点，因此它本质上是循环的。

例子：

C

      
        
            struct Node {
    int
                  data;
    struct Node* next;
};
 
struct CircularLinkedList {
    struct Node* head;
};
 
void add_node(struct CircularLinkedList* list, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
 
    if
                  (list->head == NULL) {
        list->head = new_node;
        new_node->next = new_node;
        return;
    }
 
    struct Node* current = list->head;
                
 
    while (current->next != list->head) {
        current = current->next;
    }
 
    current->next = new_node;
    new_node->next = list->head;
}

          

      
    

C++

      
        
            class Node {
public:
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
                
};
 
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {}
 
void add_node(int data) {
    Node* new_node = new Node(data);
    if
                  (head == nullptr) {
        head = new_node;
        new_node->next = head;
        return;
    }
    Node* current = head;
    while (current->next != head) {
                
        current = current->next;
    }
    current->next = new_node;
    new_node->next = head;
}
};

          

      
    

Java

      
        
            class Node {
    public
                  int data;
    public
                  Node next;
 
    public
                  Node(int d) {
        data = d;
        next = null;
                
    }
}
 
class CircularLinkedList {
    public
                  Node head;
 
    public
                  CircularLinkedList() {
        head = null;
                
    }
 
    public
                  void add_node(int data) {
        Node new_node = new Node(data);
        if (head == null) {
            head = new_node;
            new_node.next = head;
            return;
        }
        Node current = head;
        while (current.next != head) {
            current = current.next;
        }
        current.next = new_node;
        new_node.next = head;
    }
}

          

      
    

Python

      
        
            class Node:
  def __init__(self, data):
    self.data =
                  data
    self.next
                  = None
 
class CircularLinkedList:
  def __init__(self):
    self.head =
                  None
     
  def add_node(self, data):
    new_node = Node(data)
    if
                  self.head is None:
      self.head =
                  new_node
      new_node.next = self.head
                
      return
    current = self.head
    while
                  current.next != self.head:
      current = current.next
    current.next = new_node
    new_node.next = self.head
                

          

      
    

Javascript

      
        
            class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
 
class CircularLinkedList {
                
  constructor() {
    this.head = null;
  }
 
  add_node(data) {
    const new_node = new Node(data);
    if
                  (this.head === null) {
      this.head = new_node;
      new_node.next = this.head;
      return;
    }
    let current = this.head;
    while
                  (current.next !== this.head) {
      current = current.next;
    }
    current.next = new_node;
    new_node.next = this.head;
  }
}

          

      
    

C#

      
        
            public class Node
{
    public
                  int data;
    public
                  Node next;
 
    public
                  Node(int d)
                
    {
        data = d;
        next = null;
                
    }
}
 
public class CircularLinkedList
{
    public
                  Node head;
 
    public
                  CircularLinkedList()
    {
        head = null;
                
    }
 
    public
                  void add_node(int data)
    {
        Node new_node = new Node(data);
 
        if (head == null)
        {
            head = new_node;
            new_node.next = head;
            return;
        }
 
        Node current = head;
 
        while (current.next != head)
        {
            current = current.next;
        }
 
        current.next = new_node;
        new_node.next = head;
    }
}

          

      
    

循环双向静态链表： 循环双向静态链表是双向静态链表和循环静态链表的组合。这意味着这个静态链表是双向的，包含两个指针，最后一个指针指向第一个指针。

链接列表最常用于：

静态链表因其有效的插入和删除而被广泛使用。
与> 数组数据结构相比，静态链表中的插入和删除非常有效并且时间复杂度更低。
这种数据结构很简单，也可以用来实现栈、队列和其他抽象数据结构。

静态链表的应用：

静态链表用于实现堆栈和队列。
它用于树和图的各种表示。
它用于动态内存分配（空闲块的静态链表）。
它用于表示稀疏矩阵。
它用于多项式的操作。
它还用于对长整数执行算术运算。
它用于查找网络中的路径。
在操作系统中，它们可用于内存管理、进程调度和文件系统。
静态链表可用于提高需要频繁从大型数据集合中插入或删除项目的算法的性能。
实现 LRU 缓存等算法，它使用静态链表来跟踪缓存中最近使用的项目。

静态链表在现实世界中的应用：

音乐播放器中的歌曲列表链接到上一首和下一首歌曲。
在网络浏览器中，上一个和下一个网页 URL 通过上一个和下一个按钮链接。
在图像查看器中，上一个和下一个图像借助上一个和下一个按钮链接。
两个应用程序之间的切换在windows中使用“alt+tab”，在mac book中使用“cmd+tab”进行。它需要循环静态链表的功能。
在手机中，我们保存了人们的联系方式。新输入的联系方式将按正确的字母顺序排列。这可以通过链接列表来实现，以将联系人设置在正确的字母位置。
我们在文档中所做的修改实际上是作为双向静态链表中的节点创建的。我们可以简单地通过按 Ctrl+Z 来使用撤消选项来修改内容。这是通过静态链表的功能来完成的。

静态链表的优点：

静态链表是计算机科学中流行的数据结构，与其他数据结构（例如数组）相比具有许多优点。静态链表的一些主要优点是：

动态大小：静态链表没有固定的大小，因此您可以根据需要添加或删除元素，而不必担心列表的大小。当您需要使用大小可以动态更改的项目集合时，这使得链接列表成为一个不错的选择。
高效的插入和删除：在静态链表中插入或删除元素快速高效，因为您只需要修改下一个节点的引用，这是一个 O(1) 的操作。
内存效率：静态链表仅使用所需的内存，因此与数组相比，它们的内存效率更高，数组具有固定大小，如果未使用所有元素，则可能会浪费内存。
易于实现：与树和图等其他数据结构相比，静态链表的实现和理解相对简单。
灵活性：静态链表可用于实现各种抽象数据类型，例如堆栈、队列和关联数组。
易于导航：可以轻松遍历链接列表，从而更轻松地查找特定元素或对列表执行操作。

总之，静态链表是一种强大且灵活的数据结构，与其他数据结构相比具有许多优势，使其成为解决许多数据结构和算法问题的绝佳选择。

静态链表的缺点：

静态链表是计算机科学中流行的数据结构，但与任何其他数据结构一样，它们也有一定的缺点。静态链表的一些主要缺点是：

访问时间慢：访问静态链表中的元素可能会很慢，因为您需要遍历静态链表才能找到要查找的元素，这是一个 O(n) 操作。对于需要快速访问元素的情况，这使得链接列表成为一个糟糕的选择。
指针：静态链表使用指针来引用下一个节点，这使得它们比数组更难以理解和使用。这种复杂性会使静态链表更难以调试和维护。
更高的开销：与数组相比，静态链表的开销更高，因为静态链表中的每个节点都需要额外的内存来存储对下一个节点的引用。
缓存效率低下：静态链表的缓存效率低下，因为内存不连续。这意味着当你遍历静态链表时，你不太可能在缓存中获取到你需要的数据，从而导致缓存未命中和性能下降。
需要额外的内存：静态链表的每个节点都需要一个额外的指针，这会占用额外的内存。当您处理大型数据集时，这可能是一个问题，因为指针所需的额外内存会很快增加。

总之，静态链表是一种强大而灵活的数据结构，但它们有一定的缺点，在决定是否使用它们时需要考虑到。例如，如果您需要快速访问时间，数组可能是更好的选择，但如果您需要频繁插入或删除元素，静态链表可能是更好的选择。