Lineala Listes: Chapitre 2

• Chapter 2 studies linear lists

2.1 Basic Concepts of Linear Lists

• A linear list is a limited sequence of data elements with the same characteristics.
• The same characteristics: all elements belong to the same data type.
• Limited: the number of data elements is limited.
• Sequence: data elements are uniquely determined by the logical sequence number. A linear list can have elements with the same value.
• The number of elements contained in a linear list is length, indicated by n, where n≥0.
• When n=0, the linear list is an empty list, that is, the table does not contain any elements.
• The logical representation is (a1, a2,..., ai, ai+1,..., an).
• ai (1≤i≤n) shows the i-th (i indicates the logical position) element

2.1.2 Linear List Operations

• InitList(&L): Constructs an empty linear list L.
• DestroyList(&L): Frees the memory space occupied by the linear list L.
• ListEmpty(L): Returns true if L is an empty list, false otherwise.
• ListLength(L): Returns the number of elements n in L.
• DispList(L): Sequentially displays the domain of values of each node in L when the linear list L is not empty.
• GetElem(L, i, &e): Returns the value of the i-th (1≤i≤n) element in L using e.
• LocateElem(L, e): Returns the logical position of the first value domain equal to e in L; if such an element does not exist, returns 0.
• ListInsert(&L, i, e): Inserts a new element e before the i-th (1≤i≤n) element in L; the length of L is increased by 1.
• ListDelete(&L, i, &e): Deletes the i-th (1≤i≤n) element in L and returns its value with e; the length of L is decreased by 1.
• Programmers can directly use it to store data as a container for storing data.
• Programmers can directly use its basic operations to accomplish more complex functions.
• ADT for linear lists includes linear list ADT = logical structure + basic operations (operation description)

2.2 Sequential Storage Structure of Linear Lists

• Store all elements in the linear list with a sequential storage method, storing sequentially in a contiguous storage space in memory. Data member stores elements, length stores the sequence's actual length.
• Logical and physical positions differ by 1.

2.2.2 Implementation of Sequence List Operations

• To create a sequence list, a[0..n-1] creates a sequence list L as a whole

• Function prototype is void CreateList(SqList *&L, ElemType a[], int n)

• Sequence list pointed is passed by pointer.

• To initialize a sequence list, this operation constructs an empty sequence list L with the member length set to 0.

• To destroy a sequence list, this operation frees the memory space occupied by the linear list L via function void DestroyList(SqList *&L)

• To determine if a list is empty, this operation returns returns true if L is an empty sequence list, false if it is not via the function bool ListEmpty(SqList *L)

• To retrieves the length of a linear list via function int ListLength(SqList *L), this operation returns the length of the sequence list L, it simply returns the length member's value.

• To output a linear list, via the function void DispList(SqList *L), this operation displays the value of each element in L when the sequence list L is not empty.

• Retrieves the value of a data element at a certain point, via the function bool GetElem(SqList *L, int i, ElemType &e), this operation returns the value of the i-th (1≤i≤ListLength(L)) element in L and stores it in e.

• With O(1) complexity, it embodies the random access feature.

• When locating an element's value using int LocateElem(SqList *L, ElemType e), it searches through via the sequential order, starting from the 1st value, the logical order of the element that equals e; Returns value is 0.

• To insert data, using bool ListInsert(SqList *&L, int i, ElemType e) the operation inserts the element, e.

• The time complexity of moving existing elements is relevant to the list L->length and insert position 'i'

• When i = n+1, the number of moves = 0

• When i = 1, the number of moves = n (max value)

• Best time complexity is O(1)

• The worst algorithms time complexity is O(n)

• When deletion is performed using bool ListDelete(SqList *&L , int i, ElemType &e), this operation deletes the i-th (1 ≤ i ≤ ListLength(L)) element of the sequential list L.

• When i = n, the number of moves is 0

• When i=1, the number of moves will be n-1.

• The best time complexity for the deletion algotithm = 0(1)

• The worst time complexity = 0(n)

• When performing list algorithm design, take note that the data should be stored with sequence list storage and use the fundamental sequence table to complete tasks.

Example Algorithms

• Given a list of length n, design an algorithm with time complexity of 'O(n) and space complexity of 'O(1) to remove all elements in the list of value, 'x'.

• A solution requires moving all elements, resulting in 'O(n*n) time complexity with space complexity unaffected!

• Alternatively moving all non-'x' valued elements creates 'O(n)' Space & time complexity!

• Solution Remove all values equal to "x", with k tracking elements.

  • Implementation is akin to re-establishing the sequence!

• A secondary solution using k tracks a number of elements equal to x during the A-scan and statistic collection, and uses this shift non x terms.

• Given list with 10 intergers, take the 1st as the median, with all smaller or equal to, to the left, and the greater elements to it's right

• pivot = 'L' -> data[0] uses 0 - 9 scan for less than values & greater values while exchanging elements!

  • Function is void move1(SqList *&L)

• Alternatively pivots can be moved to front or behind pivot = 'L' -> data[0] via Function 'void move2(SqList '&L')' and while the algorithm scales in 'O(n)', the first method is preferred due to fewer record moves overall!