Data structure - linear list / linked list

  • The same problem can have different representation (storage) methods
  • There is a common problem: the organization and management of ordered linear sequences

1. what is a linear table?

Linear List: a linear structure consisting of ordered sequences of data elements of the same type

  • The number of elements in a table is called the length of a linear table
  • When a linear table has no elements, it is called an empty table
  • The starting position of a table is called the header, and the ending position of a table is called the footer

2. abstract data type description of linear table

  • Type name: linear table (List)
  • Data object set: a linear table is an ordered sequence of n (≥ 0) elements (a1, a2,..., an)
  • Operation set: linear table L ∈ List, integer i represents position, element X ∈ ElementType
    1. List MakeEmpty(): initializes an empty linear table L
    2. ElementType FindKth(int K,List L): returns the corresponding element according to the bit order K
    3. int Find(ElementType X,List L): find the first occurrence position of X in the linear table L
    4. void Insert(ElementType X,int i,List L): inserts a new element X before bit sequence I
    5. void Delete(int i,List L): deletes the elements of the location order I
    6. int Length(List L): returns the length n of the linear table L
2.1 implementation of sequential storage of linear tables

Use the continuous storage space of the array to store the elements of the linear table in sequence

typedef struct LNode *List;

struct LNode
{
	ElementType Data[MAXSIZE];
	int Last;
};

struct LNode L;
List PtrL;

Accessing elements with subscript I: L.Data[i] or ptrl->data[i]
Length of linear table: L.Last+1 or ptrl->last+1

Implementation of main operations

1. initialization (create an empty sequence table)

List MakeEmpty()
{
	List PtrL;
	PtrL = (List)malloc(sizeof(struct LNode));
	PtrL->Last = -1;
	return PtrL;
}

2. find

int Find(ElementType X,List PtrL)
{
	int i=0;
	while(i<=PtrL->Last && PtrL->Data[i]!=X)
		i++;
	if(i > PtrL->Last) return -1; /*If not, return -1*/
	else return i; /*The storage location is returned after finding*/
}

The average number of successful comparisons is (n+1)/2, and the average time performance is O(n)

3. insert (insert a new element with a value of X at the ith position)

void Insert(ElementType X,int i,List PtrL)
{
	int j;
	if(PtrL->Last == MAXSIZE -1) /*The tablespace is full and cannot be inserted*/
	{
		printf("Table full");
		return;
	}

	if(i<1 || i>PtrL->Last+2)	/*Check the legitimacy of the insertion position*/
	{
		printf("Illegal location");
		return;
	}

	for(j=PtrL->Last;j>=i-1;j--)
		PtrL->Data[j+1] = PtrL->Data[j]; /*Move ai~an backward in reverse order*/
	PtrL->Data[i-1] = X;	/*New element insert*/
	PtrL->Last++;			/*Last Still point to last element*/
	return;
}

The average number of moves is n/2, and the average time performance is O(n)

4. delete (delete the element at position i of the table)

void Delete(int i,List PtrL)
{
	int j;
	if(i<1 || i>PtrL->List+1)
	{
		printf("No no%d Elements",&i);
		return;
	}
	for(j=i;j<=PtrL->Last;j++)
		PtrL->Data[j-1] = PtrL->Data[j]; /*Move ai+1~an forward*/
	PtrL->Last--;						 /*Last Still point to last element*/
	return;
}
2.2 chain storage implementation of linear table

Two logically adjacent elements are not required to be physically adjacent; The logical relationship between data elements is established through "chain". You do not need to move data elements to insert or delete, but only need to modify the "chain".

typedef struct LNode *List;

struct LNode
{
	ElementType Data;
	List Next;
};

struct LNode L;
List PtrL;
Implementation of main operations

1. calculate meter length

int Length(List PtrL)
{
	List p = PtrL; /* p Point to the first node of the table */
	int j=0;
	while(p)
	{
		p = p->Next;
		j++;			/*The current p points to the j-th node*/
	}
	return j;
}

Time performance is O(n)

2. find
(1) Find by sequence number: FindKth

List FindKth(int K,List PtrL)
{
	List p = PtrL;
	int i=1;
	while(p!=NULL && i<K)
	{
		p = p->Next;
		i++;
	}
	if(i==K) return p; /*Find the kth and return the pointer*/
	else return NULL; /*Otherwise, return null*/
}

(2) Find by value: find

List Find(ElementType X,List PtrL)
{
	List p=PtrL;
	while(p!=NULL && p->Data != X)
		p = p->Next;
	return p;
}

Time performance is O(n)

3. insert (insert a new node with the value of X after the i-1 node)

List Insert(ElementType X,int i,List PtrL)
{
	List p,s;
	if(i==1) /* Insert new node in header */
	{
		s=(List)malloc(sizeof(struct LNode)); /* Application and filling node */
		s->Data = X;
		s->Next = PtrL;
		return s;	/* Return new header pointer */
	}

	p = FindKth(i-1,PtrL);	/* Find the i-1 node */
	if(p==NULL)				/* The i-1 does not exist and cannot be inserted */
	{	
		printf("parameter i error");
		return NULL;
	}
	else
	{
		s = (List)malloc(sizeof(struct LNode)); /* Application and filling node */
		s->Data = X;
		s->Next = p->Next;		/* The new node is inserted after the i-1 node */
		p->Next = s;
		return PtrL;
	}
}

4. delete (delete the node at the ith position of the linked list)


List Delete(int i ,List PtrL)
{
	List p,s;
	if(i==1)					/* If you want to delete the first node */
	{
		s = PtrL;				/* s Point to the first node */
		if(PtrL!=NULL) PtrL = PtrL->Next; /* Delete from linked list */
		else return NULL;
		free(s)		/* Release deleted nodes */
		return PtrL;
	}
}
2.3 Generalized List

  • Generalized table is a generalization of linear table
  • For a linear table, n elements are basic single elements
  • In a generalized table, these elements can be not only single elements but also another generalized table

typedef struct GNode *GList;
struct GNode
{
	int Tag;	/* Flag field: 0 indicates that the node is a single element, 1 indicates that the node is a generalized table */
	union{		/* The sub table pointer field Sublist is multiplexed with the single element Data field Data, that is, the shared storage space */
		ElementType Data;
		GList SubList;
	}URegion;
	GList Next;		/* Point to subsequent nodes */
}
2.4 multi linked list

Multi linked list: nodes in the linked list may belong to multiple chains at the same time

  • There are multiple pointer fields of nodes in the multi linked list. For example, the previous example includes the Next and SubList pointer fields;
  • However, a linked list with two pointer fields is not necessarily a multi linked list. For example, a two-way linked list is not a multi linked list

Multiple linked lists have a wide range of uses: basically, relatively complex data structures such as trees and graphs can be stored in the form of multiple linked lists.


  • Study notes on data structure by Chen Yue and heqinming of Zhejiang University

Tags: data structure linked list

Posted by xiaix on Tue, 31 May 2022 02:45:46 +0530