什么是链表？
- 链表是用于存储数据集合的线性数据结构
- 连续的元素由指针连接
- 最后一个元素指向 空**
- 每个元素都是单独的对象，称为节点
- 链表中的每个节点由两部分组成 -数据 -参考下一个节点
如何计算链表的长度？
有两种方法可以确定链表的长度：
1.迭代法 2.递归方法
迭代链表长度
我们将使用链表遍历来找出链表的长度。
- Head指向列表的第一个节点。
- 用值0初始化COUNT变量
- 使用HEAD初始化TEMP变量
- 当我们访问每个节点时，Count变量的值加1。
- 当我们达到NULL时停止该进程。
- 请勿更改头部参考。
Java代码
1package com.journaldev.ds;
2
3public class MyLinkedList {
4
5 public class Node {
6
7 int data;
8
9 Node next;
10
11 }
12
13 public Node head;
14 public Node tail;
15 public int size;
16
17 public int getFirst() throws Exception {
18
19 if (this.size == 0) {
20
21 throw new Exception("linked list is empty");
22 }
23
24 return this.head.data;
25 }
26
27 public int getLast() throws Exception {
28
29 if (this.size == 0) {
30
31 throw new Exception("linked list is empty");
32 }
33 return this.tail.data;
34 }
35
36 public void display() {
37
38 Node temp = this.head;
39 while (temp != null) {
40 System.out.println(temp.data + " ");
41 temp = temp.next;
42 }
43 }
44
45 public void addFirst(int item) {
46
47 Node nn = new Node();
48
49 nn.data = item;
50 if (this.size == 0) {
51 this.head = nn;
52 this.tail = nn;
53 this.size = this.size + 1;
54
55 } else {
56
57 nn.next = this.head;
58
59 this.head = nn;
60
61 this.size = this.size + 1;
62
63 }
64
65 }
66
67 public int length() {
68
69 Node temp = this.head;
70 int count = 0;
71 while (temp != null) {
72 count++;
73 temp = temp.next;
74 }
75 return count;
76 }
77
78 public static void main(String[] args) {
79
80 MyLinkedList ll = new MyLinkedList();
81
82 ll.addFirst(10);
83
84 ll.addFirst(20);
85
86 ll.addFirst(30);
87
88 ll.addFirst(40);
89
90 ll.addFirst(50);
91
92 System.out.println("Length of Linked List is " + ll.length());
93
94 }
95
96}
C语言代码
1#include <stdio.h>
2
3#include <stdlib.h>
4
5/* A structure of linked list node */
6
7struct node {
8
9 int data;
10
11 struct node *next;
12
13} *head;
14
15void initialize(){
16
17 head = NULL;
18
19}
20
21/*
22
23Inserts a node in front of a singly linked list.
24
25*/
26
27void insert(int num) {
28
29 /* Create a new Linked List node */
30
31 struct node* newNode = (struct node*) malloc(sizeof(struct node));
32
33 newNode->data = num;
34
35 /* Next pointer of new node will point to head node of linked list */
36
37 newNode->next = head;
38
39 /* make new node as the new head of linked list */
40
41 head = newNode;
42
43 printf("Inserted Element : %d\n", num);
44
45}
46
47int getLength(struct node *head){
48
49 int length =0;
50
51 while(head != NULL){
52
53 head = head->next;
54
55 length++;
56
57 }
58
59 return length;
60
61}
62
63/*
64
65Prints a linked list from head node till the tail node
66
67*/
68
69void printLinkedList(struct node *nodePtr) {
70
71 while (nodePtr != NULL) {
72
73 printf("%d", nodePtr->data);
74
75 nodePtr = nodePtr->next;
76
77 if(nodePtr != NULL)
78
79 printf("-->");
80
81 }
82
83}
84
85int main() {
86
87 initialize();
88
89 /* Creating a linked List*/
90
91 insert(8);
92
93 insert(3);
94
95 insert(2);
96
97 insert(7);
98
99 insert(9);
100
101 printf("\nLinked List\n");
102
103 printLinkedList(head);
104
105 printf("\nLinked List Length : %d", getLength(head));
106
107 return 0;
108
109}
输出
递归求解链表长度
基本情况：
- 最后一个节点指向空值
- 返回0
递归大小写：
- 在每个步骤中，将当前节点的值更新为下一个节点
- Call=1+Fun(Curr.Next)
示例：链表中有3个元素：LL1、LL2和LL3。我们将观察在进行递归调用时内存堆栈中发生了什么。内存堆栈 ：
main函数调用LL1，LL1调用LL2，LL2调用LL3，LL3调用null值。当达到最大值时，我们从这里返回。LL3返回0，LL3返回1，LL2返回2，LL1返回2。LL1最终将3返回给main函数。
Java中的代码
1package com.journaldev.ds;
2
3public class MyLinkedList {
4
5 public class Node {
6
7 int data;
8
9 Node next;
10
11 }
12
13 public Node head;
14
15 public Node tail;
16
17 public int size;
18
19 public int getfirst() throws Exception {
20
21 if (this.size == 0) {
22
23 throw new Exception("linked list is empty");
24
25 }
26
27 return this.head.data;
28
29 }
30
31 public int RemoveFirst() throws Exception {
32
33 if (this.size == 0) {
34
35 throw new Exception("LL is empty");
36
37 }
38
39 Node temp = this.head;
40
41 if (this.size == 1) {
42
43 this.head = null;
44
45 this.tail = null;
46
47 size = 0;
48
49 } else {
50
51 this.head = this.head.next;
52
53 this.size--;
54
55 }
56
57 return temp.data;
58
59 }
60
61 public void addFirst(int item) {
62
63 Node nn = new Node();
64
65 nn.data = item;
66
67 if (this.size == 0) {
68
69 this.head = nn;
70
71 this.tail = nn;
72
73 this.size = this.size + 1;
74
75 } else {
76
77 nn.next = this.head;
78
79 this.head = nn;
80
81 this.size = this.size + 1;
82
83 }
84
85 }
86
87 public int lengthUsingRecursiveApproach (){
88
89 return lengthUsingRecursiveApproach(this.head);
90
91 }
92
93 private int lengthUsingRecursiveApproach(Node curr) {
94
95 // TODO Auto-generated method stub
96
97 if (curr == null) {
98
99 return 0;
100
101 }
102
103 return 1 + lengthUsingRecursiveApproach (curr.next);
104
105 }
106
107 public static void main(String[] args) {
108
109 MyLinkedList ll = new MyLinkedList();
110
111 // insert elements into the Linked List
112
113 ll.addFirst(10);
114
115 ll.addFirst(20);
116
117 ll.addFirst(30);
118
119 ll.addFirst(40);
120
121 ll.addFirst(50);
122
123 // Length of List
124
125 System.out.println("Recursive Approach length " + ll.lengthUsingRecursiveApproach(ll.head));
126
127 }
128
129}
C语言代码
1#include <stdio.h>
2
3struct Node
4
5{
6
7 int data;
8
9 struct Node* next;
10
11};
12void push(struct Node** head_ref, int new_data)
13{
14
15 struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
16
17 new_node->data = new_data;
18
19 /* link the old list of the new node */
20
21 new_node->next = (*head_ref);
22
23 (*head_ref) = new_node;
24
25}
26
27int getCount(struct Node* head)
28
29{
30
31 // Base case
32
33 if (head == NULL)
34
35 return 0;
36
37 return 1 + getCount(head->next);
38
39}
40
41int main()
42
43{
44
45 struct Node* head = NULL;
46
47 push(&head, 1);
48
49 push(&head, 3);
50
51 push(&head, 1);
52
53 push(&head, 2);
54
55 push(&head, 1);
56
57 printf("count of nodes is %d", getCount(head));
58
59 return 0;
60
61}
输出
时间复杂度
O(N)在递归和迭代解中，正如我们所需要的那样，只需一次遍历即可知道长度。