單鏈表遍歷

單鏈表 (Single linked list)

Single linked list contains a number of nodes where each node has a data field and a pointer to next node. The link of the last node is to NULL, indicates end of list.

單個鏈表包含許多節點，其中每個節點都有一個數據字段和一個指向下一個節點的指針。 最后一個節點的鏈接為NULL，表示列表結尾。

單鏈表結構 (Single linked list structure)

The node in the linked list can be created using struct.

可以使用struct創建鏈接列表中的節點。

struct node{
// data field, can be of various type, here integer
int data; 
// pointer to next node
struct node* next; 
};

鏈表上的基本操作 (Basic operations on linked list)

• Traversing

  遍歷

• Inserting node

  插入節點

• Deleting node

  刪除節點

單個鏈表的遍歷技術 (Traversing technique for a single linked list)

• Follow the pointers

  跟隨指針

• Display content of current nodes

  顯示當前節點的內容

• Stop when next pointer is NULL

  當下一個指針為NULL時停止

C代碼遍歷鏈接列表并計算節點數 (C code to traverse a linked list and count number of nodes )

#include <stdio.h>
#include <stdlib.h>
struct node{
int data; // data field
struct node *next;
};
void traverse(struct node* head){
struct node* current=head; // current node set to head
int count=0; // to count total no of nodes
printf("\n traversing the list\n");
//traverse until current node isn't NULL
while(current!=NULL){ 
count++; //increase node count
printf("%d ",current->data);
current=current->next; // go to next node
}
printf("\ntotal no of nodes : %d\n",count);
}
struct node* creatnode(int d){
struct node* temp= (struct node*) malloc(sizeof(struct node));
temp->data=d;
temp->next=NULL;
return temp;
}
int main()
{
printf("creating & traversing linked list\n");
//same linked list is built according to image shown
struct node* head=creatnode(5);
head->next=creatnode(10);
head->next->next=creatnode(20);
head->next->next->next=creatnode(1);
traverse(head);
return 0;
}

Output

輸出量

creating & traversing linked list
traversing the list
5 10 20 1
total no of nodes : 4

Time complexity:

時間復雜度：

O(n), for scanning the list of size n

O(n) ，用于掃描大小為n的列表

Space complexity:

空間復雜度：

O(1), no additional memory required

O(1) ，不需要額外的內存

翻譯自: https://www.includehelp.com/data-structure-tutorial/single-linked-list-and-its-basic-operations-with-traversing-implementation.aspx

單鏈表遍歷