MindMap Gallery Data structure - linear table
This is a mind map about data structure - linear tables, including linear tables, stacks and queues, which are all linear tables with limited operations.
Edited at 2023-11-27 15:48:15This infographic, created using EdrawMax, outlines the pivotal moments in African American history from 1619 to the present. It highlights significant events such as emancipation, key civil rights legislation, and notable achievements that have shaped the social and political landscape. The timeline serves as a visual representation of the struggle for equality and justice, emphasizing the resilience and contributions of African Americans throughout history.
This infographic, designed with EdrawMax, presents a detailed timeline of the evolution of voting rights and citizenship in the U.S. from 1870 to the present. It highlights key legislative milestones, court decisions, and societal changes that have expanded or challenged voting access. The timeline underscores the ongoing struggle for equality and the continuous efforts to secure voting rights for all citizens, reflecting the dynamic nature of democracy in America.
This infographic, created using EdrawMax, highlights the rich cultural heritage and outstanding contributions of African Americans. It covers key areas such as STEM innovations, literature and thought, global influence of music and arts, and historical preservation. The document showcases influential figures and institutions that have played pivotal roles in shaping science, medicine, literature, and public memory, underscoring the integral role of African American contributions to society.
This infographic, created using EdrawMax, outlines the pivotal moments in African American history from 1619 to the present. It highlights significant events such as emancipation, key civil rights legislation, and notable achievements that have shaped the social and political landscape. The timeline serves as a visual representation of the struggle for equality and justice, emphasizing the resilience and contributions of African Americans throughout history.
This infographic, designed with EdrawMax, presents a detailed timeline of the evolution of voting rights and citizenship in the U.S. from 1870 to the present. It highlights key legislative milestones, court decisions, and societal changes that have expanded or challenged voting access. The timeline underscores the ongoing struggle for equality and the continuous efforts to secure voting rights for all citizens, reflecting the dynamic nature of democracy in America.
This infographic, created using EdrawMax, highlights the rich cultural heritage and outstanding contributions of African Americans. It covers key areas such as STEM innovations, literature and thought, global influence of music and arts, and historical preservation. The document showcases influential figures and institutions that have played pivotal roles in shaping science, medicine, literature, and public memory, underscoring the integral role of African American contributions to society.
linear structure
linear table
Definition: It is a logical structure, a finite sequence of n data elements of the same data type
sequential storage
Sequence table (logical sequence and physical sequence are the same)
Features
Random access, easy to find
High storage density
Adding or deleting is troublesome
Expansion is troublesome (malloc will increase time complexity)
Method to realize
static allocation
Define a fixed-length array and the system automatically reclaims space
dynamic allocation
Use malloc and free functions (appear in pairs)
Basic operations
insert
Best O(1), worst O(n), average O(n)
delete
Best O(1), worst O(n), average O(n)
Find
Bitwise search
Best/Worst/Average O(1)
Find by value
Best O(1), worst O(n), average O(n)
The main time cost comes from moving elements
chain storage
Linked list (logical order and physical order do not need to be the same)
Features
Low storage density
Easy to insert and delete
Flexible storage
Single list
Create (insert)
Header plug-in method established
O(n)
Tail insertion method established
O(n)
Find
Find by value
O(n)
Bitwise search
O(n)
delete
O(n)
Ask for table length
Just add a counter
O(n)
Double linked list
insert
O(1)
delete
O(1)
Instead of traversing the singly linked list, you can directly find the predecessor pointer and modify it.
Find
O(n)
circular linked list
Circular singly linked list
Point the head node L to the tail, so the time complexity of the tail operation is O(n)
Circular doubly linked list
static linked list
Linked list implemented with array, cursor represents array subscript
The main time overhead comes from moving elements, so in dealing with actual problems, the efficiency of linked list insertion/deletion is higher than that of sequential list
Both stacks and queues are linear tables with limited operations.
stack
queue