单链表结点中只有一个指向其后继的指针，使得单链表只能从前往后依次遍历。要访问某个结点的前驱(插入、删除操作时)，只能从头开始遍历，访问前驱的时间复杂度为 O(n)。
为了克服单链表的这个缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其直接前驱和直接后继。

双链表的主要特性

双向遍历由于每个节点都有前后两个指针，因此可以在列表中双向遍历，无需像单链表那样只能从头节点开始向前遍历。
插入与删除的便捷性：在双链表中插入或删除一个节点时，只需改变相应节点的前后节点的指针指向即可，操作相对简单高效。

数据结构

data：数据域，也是节点的值
prior：指针域，指向前一个结点的指针
next：指针域，指向下一个结点的指针

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct DNode {
  int data; // 数据
  struct DNode *prior, *next; // 前驱和后继指针
} DNode, *DLinkList;
pTemp = (DNode *)malloc(sizeof(DNode));
pTemp->data = x;
pTemp->next = pHead->next;
pTemp->prior = pHea
// 完整代码：https://totuma.cn

链表结构

💡双链表在单链表结点中增加了一个指向其前驱的指针prior ，因此双链表的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为“链”变化时也需要对指针 prior 做出修改，其关键是保证在修改的过程中不断链。 此外,双链表可以很方便地找到当前结点的前驱，因此，插入、除操作的时间复杂度仅为 O(1)。

双链表的基本操作实现

单链表的节点在需要时动态分配内存，这意味着不需要像数组那样在创建时预先分配一大片连续内存。因此，单链表在内存使用上更加灵活，可以有效应对内存碎片和动态增长的问题。

由于链表节点是在需要时分配的，可以避免数组因初始化大小不确定而造成的内存浪费。例如，如果数组大小初始化过大，未使用的部分将浪费内存；若初始化过小，则可能需要频繁重新分配和复制。

每个节点需要一个指针域来存储对下一个节点的引用，这意味着相比于数组，单链表在每个节点上都会有额外的内存开销。对于存储小数据的场景，这个开销相对较大，可能导致内存利用率下降。

按位序插入结点

该函数用于在双向链表中按指定位置插入一个新元素。(注意区分位置和下标：位置从1开始，下标从0开始)

在位置 i 插入元素 e，其中 i=1 表示插入到表头，i=length+1 表示插入到表尾。

重点注意下链表为空和不为空时的处理逻辑

插入时链表空和不空时的区别

按位序插入结点 | 可视化完整可视化

2.3 Detailed Explanation of Doubly Linked Lists - Linear Lists Tutorial Visualize your code with animations

Understanding Linked Lists: A Beginner-Friendly Guide to Linear Data Structures

Welcome to our comprehensive guide on linked lists, one of the most fundamental data structures in computer science. If you are learning data structures and algorithms, mastering the linked list is a crucial step. This article will explain what a linked list is, how it works, its unique characteristics, and where it is used in real-world applications. We will also show you how our Data Structure Visualization Platform can help you understand linked lists through interactive animations and hands-on practice.

What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are stored in a sequence. Unlike arrays, linked list nodes are not stored in contiguous memory locations. Instead, each node contains two parts: the data itself and a reference (or pointer) to the next node in the sequence. This linking mechanism allows the list to grow and shrink dynamically without the need for memory reallocation.

The simplest form is the singly linked list, where each node points only to the next node. There are also doubly linked lists, where nodes point to both the next and previous nodes, and circular linked lists, where the last node points back to the first node. Each variant offers different trade-offs in terms of memory usage and operational efficiency.

How a Linked List Works

Imagine a chain of paper clips. Each clip holds a piece of data, and the connection between clips represents the pointer. To traverse the list, you start at the first node, called the head, and follow the pointers until you reach a node whose pointer is null (or points back to the head in a circular list).

When you insert a new node, you simply adjust the pointers of the surrounding nodes. For example, to insert a node between node A and node B, you make node A's pointer point to the new node, and the new node's pointer point to node B. Deletion works similarly: you bypass the node you want to remove by updating the pointer of the previous node to skip it.

Key Characteristics of Linked Lists

Dynamic Size: Unlike arrays, linked lists can grow or shrink during program execution. You do not need to predefine the size, which makes them ideal for situations where the number of elements is unknown or changes frequently.

Efficient Insertions and Deletions: Inserting or deleting a node at the beginning or middle of a linked list is an O(1) operation if you have a reference to the node. In contrast, arrays require shifting elements, which takes O(n) time.

Sequential Access: Linked lists do not support random access. To access the nth element, you must traverse from the head, resulting in O(n) time complexity. This is a major drawback compared to arrays, which offer O(1) random access.

Memory Overhead: Each node requires extra memory for the pointer(s), which can be significant for small data types. For example, storing a single integer in a linked list node may require 8 bytes for the integer and 8 bytes for the pointer (on a 64-bit system), effectively doubling the memory usage.

No Memory Fragmentation: Because nodes are allocated individually on the heap, linked lists can use memory more efficiently in environments with many small allocations, though they may suffer from fragmentation over time.

Types of Linked Lists

Singly Linked List: Each node has one pointer to the next node. This is the simplest and most memory-efficient variant, but traversal is only possible in one direction.

Doubly Linked List: Each node has two pointers: one to the next node and one to the previous node. This allows bidirectional traversal and makes deletion of a node more efficient (O(1) if you have a pointer to the node). However, it uses more memory.

Circular Linked List: The last node's pointer points back to the first node, forming a circle. This is useful for applications that require cyclic traversal, such as round-robin scheduling.

Header Linked List: A special node called the header node is added at the beginning. This node does not contain meaningful data but simplifies certain operations, such as insertion and deletion at the head.

Common Operations and Their Time Complexity

Traversal: O(n) - You must follow pointers from head to tail.

Insertion at Head: O(1) - Create a new node and update the head pointer.

Insertion at Tail (with tail pointer): O(1) - If you maintain a tail pointer, you can insert directly.

Insertion at Tail (without tail pointer): O(n) - You must traverse to the end.

Insertion in Middle: O(1) if you have a pointer to the node before the insertion point; otherwise O(n) to find that node.

Deletion at Head: O(1) - Update the head pointer to the next node.

Deletion in Middle: O(1) if you have a pointer to the node before the deletion point; otherwise O(n).

Search: O(n) - You must traverse the list sequentially.

Access by Index: O(n) - No random access is possible.

Real-World Applications of Linked Lists

Dynamic Memory Allocation: Operating systems use linked lists to track free memory blocks. When a program requests memory, the OS searches the free list for a suitable block.

Undo/Redo Functionality: Text editors and graphic design software use doubly linked lists to store the history of actions. Each action is a node, and you can move forward or backward through the history.

Music Playlists: A circular linked list is perfect for implementing a playlist that loops continuously. Each song is a node, and the last song points back to the first.

Hash Table Chaining: To handle collisions in hash tables, many implementations use linked lists to store multiple keys that hash to the same bucket.

Graph Adjacency Lists: Graphs are often represented using an array of linked lists, where each list contains the neighbors of a vertex.

Browser History: Web browsers use linked lists to store the history of visited pages, allowing users to navigate forward and backward.

Polynomial Arithmetic: Linked lists can represent polynomials, where each node stores a coefficient and an exponent. This makes addition and multiplication of polynomials efficient.

Linked List vs. Array: A Comparison

When should you use a linked list instead of an array? The answer depends on your specific requirements. If you need random access to elements, an array is the clear winner. If you frequently insert or delete elements at arbitrary positions, especially near the beginning, a linked list is more efficient.

Arrays have better cache locality because elements are stored contiguously. This means that accessing array elements is faster on modern hardware due to CPU caching. Linked lists, with their scattered memory locations, often cause cache misses, leading to slower performance in practice even if the theoretical time complexity is the same.

Memory usage is another factor. Arrays may waste memory if they are over-allocated, but they have no per-element overhead. Linked lists have pointer overhead for each node, which can be substantial for small data types.

Common Pitfalls When Learning Linked Lists

Losing the Head Pointer: Beginners often accidentally lose the reference to the head node, making the entire list inaccessible. Always keep a copy of the head pointer before performing operations.

Dangling Pointers: When deleting a node, ensure that you update the pointers of surrounding nodes correctly. A dangling pointer points to memory that has been freed, causing undefined behavior.

Null Pointer Dereference: Always check for null before accessing node fields. Traversing a list without checking for the end can cause segmentation faults.

Memory Leaks: In languages like C or C++, you must manually free memory for deleted nodes. Failing to do so causes memory leaks.

Infinite Loops: In circular linked lists, ensure that your traversal condition correctly detects when you have returned to the starting node.

How Our Data Structure Visualization Platform Helps You Learn Linked Lists

Our interactive visualization platform is designed specifically for learners like you who want to truly understand how data structures work under the hood. Here is how it can accelerate your learning of linked lists:

Step-by-Step Animation: Watch as nodes are created, linked, and unlinked in real time. Each operation is animated with clear labels showing data values and pointer addresses. You can pause, rewind, and replay operations to see exactly what happens at each step.

Visual Pointer Tracking: See how pointers change during insertions and deletions. The platform highlights the affected pointers with color-coded arrows, making it easy to understand the pointer manipulation logic.

Interactive Code Execution: Write your own linked list code in Python, Java, C++, or JavaScript, and watch the visualization update in sync with your code execution. This bridges the gap between abstract code and concrete behavior.

Pre-Built Examples: Explore a library of common linked list problems, including reversing a list, detecting cycles, merging two sorted lists, and finding the middle node. Each example comes with a step-by-step visualization and explanation.

Real-Time Memory View: See how nodes are allocated on the heap and how memory addresses are linked. This demystifies the concept of pointers and memory management.

Performance Analysis: The platform can simulate operations on large lists and show you the actual time taken, helping you understand the practical implications of time complexity.

Error Detection: When you make a mistake in your code, the platform highlights the problematic step and suggests corrections. This immediate feedback is invaluable for learning.

Getting Started with Our Platform

Using our platform to learn linked lists is straightforward. First, select "Linked List" from the data structure menu. You will see an empty canvas with a head pointer. You can either write your own code in the built-in editor or choose a pre-built example from the library.

To add nodes manually, click the "Insert" button and enter the data value. The platform will create a new node and link it according to your specifications. You can also choose to insert at the head, tail, or a specific position.

For code-based learning, paste your linked list implementation into the editor and click "Run". The platform will parse your code and visualize each operation as it executes. You can set breakpoints to pause at critical moments and inspect the state of the list.

The platform also includes a quiz mode that tests your understanding of linked list operations. You are given a scenario and must predict the outcome. The platform then shows you the correct answer with a visualization, reinforcing your learning.

Advanced Features for Deeper Understanding

Our platform goes beyond basic visualization. For advanced learners, we offer:

Algorithm Comparison: Compare the performance of different algorithms on the same linked list. For example, you can compare iterative vs. recursive traversal and see how the call stack grows in the recursive version.

Custom Test Cases: Create your own test cases with specific data patterns, such as sorted lists, lists with cycles, or lists with duplicate values. The platform will visualize how different algorithms handle these edge cases.

Multi-Threading Simulation: See how concurrent operations on a linked list can lead to race conditions. The platform simulates multiple threads and shows you exactly where synchronization is needed.

Memory Leak Detection: Run your code and the platform will flag any nodes that are not properly freed, helping you develop good memory management habits.

Exportable Diagrams: You can export any state of the linked list as an image or SVG file, perfect for study notes or sharing with classmates.

Why Visualization Matters for Learning Data Structures

Research in educational psychology shows that visual learning significantly improves comprehension and retention, especially for abstract concepts like pointers and memory allocation. When you can see the data structure changing in real time, the underlying logic becomes intuitive rather than memorized.

Many students struggle with linked lists because they try to understand pointer manipulation through code alone. Code is a static representation of dynamic behavior. Visualization bridges this gap by showing you the dynamic behavior directly. You no longer have to imagine what happens when you set "node.next = previous" – you can watch it happen.

Our platform is built on the principle that active learning is more effective than passive reading. By interacting with the visualization, writing your own code, and debugging with visual feedback, you engage multiple cognitive pathways, leading to deeper understanding.

Common Questions About Linked Lists

Q: Is a linked list faster than an array? A: It depends on the operation. Linked lists are faster for insertions and deletions at arbitrary positions, especially near the beginning. Arrays are faster for random access and traversal due to cache locality.

Q: When should I use a doubly linked list instead of a singly linked list? A: Use a doubly linked list when you need to traverse in both directions, or when you need O(1) deletion of a node given only a pointer to that node. The trade-off is extra memory for the previous pointer.

Q: Can I implement a stack or queue using a linked list? A: Yes. A singly linked list with a head pointer makes an excellent stack (LIFO). A doubly linked list with head and tail pointers makes an efficient queue (FIFO).

Q: How do I detect a cycle in a linked list? A: Use Floyd's cycle detection algorithm (tortoise and hare). Maintain two pointers, one moving one step at a time and the other moving two steps. If they meet, there is a cycle.

Q: What is a skip list? A: A skip list is a probabilistic data structure based on linked lists that allows O(log n) search, insertion, and deletion. It consists of multiple layers of linked lists, where each layer skips over some elements.

Conclusion

Linked lists are a foundational data structure that every programmer must understand. They teach you about dynamic memory allocation, pointer manipulation, and the trade-offs between different data structures. While they may seem challenging at first, our interactive visualization platform makes the learning process engaging and effective.

We encourage you to start practicing with our platform today. Begin with simple operations like insertion and traversal, then move on to more complex algorithms like reversal and cycle detection. With consistent practice and visual feedback, you will master linked lists in no time.

Remember, understanding data structures is not about memorizing code – it is about understanding the underlying mechanics. Our platform gives you the tools to see those mechanics in action. Happy learning!

按位序删除结点

该函数用于按位序删除节点的功能。具体来说，当参数 i 为 1 时，删除链表的 头节点；当 i 等于链表长度时，删除链表的 尾节点。