类的定义
在类的内部包含一个结构体，结构体包含一个指向下一结点的指针，以及一个数据域，用于存储插入链表的用户数据。
1. #pragma once 2. #include <iostream> 3. using namespace std; 4. 5. template<typename MyType> 6. class LinkedList 7. { 8. public: 9. LinkedList(); 10. ~LinkedList(); 11. public: 12. int get_length(); 13. MyType get_data(int pos); 14. int insert(MyType& node, int pos); 15. MyType delet(int pos); 16. void clear(); 17. public: 18. typedef struct ListNode 19. { 20. struct ListNode* next; 21. MyType data; 22. }ListNode; 23. private: 24. int length; 25. ListNode* head; 26. };
成员函数的实现
1. template<typename MyType> 2. LinkedList<MyType>::LinkedList() 3. { 4. this->head = new ListNode; 5. this->head->next = NULL; 6. this->length = 0; 7. } 8. 9. template<typename MyType> 10. LinkedList<MyType>::~LinkedList() 11. { 12. ListNode* pCurrent = this->head; 13. while (pCurrent != NULL) 14. { 15. ListNode* pTemp = pCurrent; 16. pCurrent = pCurrent->next; 17. delete pTemp; 18. } 19. this->length = 0; 20. } 21. 22. template<typename MyType> 23. int LinkedList<MyType>::get_length() 24. { 25. return this->length; 26. } 27. 28. template<typename MyType> 29. MyType LinkedList<MyType>::get_data(int pos) 30. { 31. ListNode* pCurrent = this->head; 32. for (int i = 0; i < pos; i++) 33. { 34. pCurrent = pCurrent->next; 35. } 36. return pCurrent->next->data; 37. } 38. 39. template<typename MyType> 40. int LinkedList<MyType>::insert(MyType& node, int pos) 41. { 42. ListNode* pCurrent = this->head; 43. for (int i = 0; i < pos; i++) 44. { 45. pCurrent = pCurrent->next; 46. } 47. ListNode* pNode = new ListNode; 48. pNode->data = node; 49. pNode->next = pCurrent->next; 50. pCurrent->next = pNode; 51. this->length++; 52. return 0; 53. } 54. 55. template<typename MyType> 56. MyType LinkedList<MyType>::delet(int pos) 57. { 58. ListNode* pCurrent = this->head; 59. for (int i = 0; i < pos; i++) 60. { 61. pCurrent = pCurrent->next; 62. } 63. MyType temp_data = pCurrent->next->data; 64. ListNode* pTemp = pCurrent->next; 65. pCurrent->next = pCurrent->next->next; 66. delete pTemp; 67. this->length--; 68. return temp_data; 69. } 70. 71. template<typename MyType> 72. void LinkedList<MyType>::clear() 73. { 74. ListNode* pCurrent = this->head; 75. while (pCurrent != NULL) 76. { 77. ListNode* pTemp = pCurrent; 78. pCurrent = pCurrent->next; 79. delete pTemp; 80. } 81. this->head = new ListNode; 82. this->head->next = NULL; 83. this->length = 0; 84. }
因为链表的结点是动态分配的，插入一个数据，就用动态构造一个结点，并把要插入的数据存到结点的数据域。所以，在插入元素和删除元素的时候需要使用new和delete来管理内存。
C语言实现链表请参考文章
另外，代码资源已经上传，可在我的资源免费下载。
