单向链表

  1 #pragma once
  2 
  3 // List.h
  4 
  5 #include <iostream>
  6 
  7 using namespace std;
  8 
  9 struct Node
 10 {
 11     int element;
 12     Node *next;
 13 };
 14 
 15 class List           //单向链表
 16 {
 17 public:
 18     List();
 19     bool empty() const;        //检查链表是否为空
 20     int front() const;        //返回链表的第一个元素
 21     int back() const;        //返回链表的最后一个元素
 22     int size() const;          //返回链表的长度
 23     Node* find(int ele);       //返回指向ele的指针
 24     void insert(int position, int ele);     //在position位置插入ele (head处于position = 0的位置)
 25     void push_back(int ele);                //在尾部插入
 26     void remove(int ele);               //删除值为ele的所有元素
 27     void clear();              //清空链表，有了这个操作之后就不要定义析构函数了
 28     void print();              //打印链表中的所有元素
 29 
 30 private:
 31     Node *head;                //头结点
 32     int length;                //链表长度
 33 };
 34 
 35 List::List()
 36 {
 37     head = new Node;        //head不能是nullptr，不然head->next是未定义的行为
 38     head->next = nullptr;
 39     length = 0;
 40 }
 41 
 42 bool List::empty() const
 43 {
 44     return (head->next) == nullptr;
 45 }
 46 
 47 int List::front() const
 48 {
 49     return (head->next)->element;
 50 }
 51 
 52 int List::back() const
 53 {
 54     Node* p = head;
 55     while (p->next != nullptr)
 56         p = p->next;
 57     return p->element;
 58 }
 59 
 60 int List::size() const
 61 {
 62     return length;
 63 }
 64 
 65 
 66 Node* List::find(int ele)
 67 {
 68     Node* p = head;
 69     while (p->next != nullptr)
 70     {
 71         p = p->next;
 72         if (p->element = ele)
 73             return p;
 74     }
 75     cout << "Not find this element!" << endl;
 76     return nullptr;
 77 }
 78 
 79 void List::insert(int position, int ele)   //在特定位置插入元素,在position位置插入一个元素
 80 {
 81     Node* p = head;
 82     for (int i = 1; i <= position - 1; ++i)
 83         p = p->next;   //获取position前一个位置的指针p
 84     Node *newNode = new Node;
 85     newNode->element = ele;
 86     newNode->next = p->next;
 87     p->next = newNode;
 88     ++length;
 89 }
 90 
 91 void List::push_back(int ele)
 92 {
 93     Node* p = head;
 94     while (p->next != nullptr)
 95         p = p->next;
 96     Node *newNode = new Node;
 97     newNode->element = ele;
 98     p->next = newNode;
 99     newNode->next = nullptr;
100     ++length;
101 }
102 
103 void List::remove(int ele)
104 {
105     Node *q = head;
106     auto p = q->next;
107 
108     while (p != nullptr)
109     {
110         if (p->element == ele)
111         {
112             q->next = p->next;
113             delete p;
114             p = q->next;
115             --length;
116         }
117         else
118         {
119             q = p;
120             p = q->next;
121         }
122     }
123 }
124 
125 void List::clear()
126 {
127     Node* p1 = head->next;
128     while (p1 != nullptr)
129     {
130         auto p2 = p1->next;
131         delete p1;
132         if (p2 != nullptr)
133             p1 = p2;
134         else break;
135     }
136     length = 0;
137 }
138 
139 void List::print()
140 {
141     Node* p1 = head->next;
142     while (p1 != nullptr)
143     {
144         cout << p1->element << ' ';
145         p1 = p1->next;
146     }
147 }

 1 //main.cpp
 2 
 3 #include <iostream>
 4 #include "List.h"
 5 
 6 using namespace std;
 7 
 8 int main()
 9 {
10     List lst;
11     lst.push_back(1);
12     lst.push_back(2);
13     lst.push_back(3);
14     lst.push_back(2);
15     lst.push_back(9);
16     lst.remove(2);
17 
18     cout << lst.size();
19 
20 
21     return 0;
22 }