Algorithms, Data Structures, Linear Structures, Stacks, Queues

Algorithms

1. Basic characteristics of an algorithm

   • Feasibility
     • The steps are implementable and the execution result meets expectations
   • Determinacy
     • The steps are unambiguous
   • Finiteness
     • It completes in a finite amount of time
   • Possessing sufficient intelligence
     • Having enough input information and initialization information

2. Complexity of an algorithm

   • Time complexity
     • The amount of computational work required to execute the algorithm
   • Space complexity
     • The memory space required to execute the algorithm

Data Structures

1. Definition: a data structure is a collection of data elements that are related to one another.

• Concepts of data structures
  • Root node
    • A node with no predecessor
  • Terminal node
    • A node with no successor
  • Internal node
    • A node other than the root node and the terminal node

Linear Structures and Non-linear Structures

1. Linear structure

   • There is exactly one root node
   • Each node has at most one predecessor and at most one successor

2. Non-linear structure: anything that does not satisfy the two conditions of a linear structure is a non-linear structure

   • Tree structure
   • Network structure

Linear Lists

1. A linear structure is also called a linear list

2. Non-empty linear list

   • It has only one root node
   • It has exactly one terminal node
   • Apart from the root node and the terminal node, every other node has exactly one predecessor and exactly one successor

Sequential Storage of Linear Lists

1. Definition: sequential storage of a linear list means storing the elements of the linear list one after another in a contiguous storage area; such a linear list is also called a sequential list

2. Characteristics of a sequential list

   • The storage space occupied by all elements in the linear list is contiguous
   • The data elements in the linear list are stored one by one in logical order within the storage space

Stacks

1. Definition: a stack is a special kind of linear list. All of its insertions and deletions are restricted to the same end of the list. The end where insertion and deletion are allowed is called the top of the stack, and the end where they are not allowed is called the bottom of the stack. When the stack contains no elements, it is called an empty stack.

2. The modification principle of a stack is last-in-first-out, or first-in-last-out

3. Basic operations on a stack: push, pop, read the top element

Queues

1. Definition: a linear list that allows insertion at one end and deletion at the other end

2. The end where deletion is allowed is called the front of the queue, and the end where insertion is allowed is called the rear of the queue

Comparison of Sequential Lists and Linked Lists

1. Sequential list

   • Advantages
     • Any node in the list can be accessed randomly
     • No extra storage space is needed to represent the logical relationships between nodes
   • Disadvantages
     • Insertion and deletion in a sequential list are very inefficient
     • The storage space of a sequential list is inconvenient to expand
     • A sequential list is not convenient for dynamic allocation of storage space

2. Linked list

   • Advantages
     • For insertion and deletion, only the pointers need to be changed; elements do not need to be moved
     • The storage space of a linked list is easy to expand and convenient for dynamic allocation

   • Disadvantages

     • Extra space is needed to represent the logical relationships between data elements, so the storage density is lower than that of a sequential list

   • Types of linked lists

     • Singly linked list
       • The links of the list run in a single direction; accessing the list requires reading sequentially from the head. A linked list is a list constructed using pointers; it is also called a node list
       • Creating a single node is very convenient; ordinary linear memory usually requires the data size to be set at creation time
       • Deleting a node is very convenient; there is no need to move the remaining data as with a linear structure
       • Accessing nodes is convenient; any data can be reached through loops or recursion, but the average access efficiency is lower than that of a linear list
     • Doubly linked list
       • Each data node has two pointers, pointing to its direct successor and direct predecessor respectively. Starting from any node in a doubly linked list, you can conveniently access its predecessor and successor nodes

   • Circular linked list

     • The last node points to the head node, forming a ring. Starting from any node in a circular linked list, you can find any other node