单向链表

简介

链表中最简单的一种是单向链表，它包含两个域，一个数据域和一个指针域，指针域指向链表中的下一个节点，最后一个节点的指针域指向一个空值

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个（需要储存反向的指针，见下面的双向链表）节点。

接下来我将以代码的形式展示单向链表的基本操作:

• 创建
• 插入
• 查找
• 删除

代码

#include <iostream>
using namespace std;

struct Node {
  int value;
  Node* next;
  Node(int num):value(num),next(nullptr) {};
  Node(){};
};
class LinkList{
public:
  void Create();
  void InsertHead(Node* );
  void InsertTail(Node* );
  Node* FindByIndex(int);
  Node* FindByValue(int);
  int GetLength();
  void DeleteByIndex(int);
  void DeleteByValueOnce(int);
  void DeleteByValueAll(int);
  void EditByIndex(int, int);
  void Print();
private:
  Node* head;
};

void LinkList::Create(){
  head = new Node();
  head->next = nullptr;
  head->value = 0;
}

void LinkList::InsertHead(Node* p){
  p->next = head->next;
  head->next = p;
  head->value++;
}

void LinkList::InsertTail(Node* p){
  Node* tail = FindByIndex(head->value);
  if (tail == nullptr) InsertHead(p);
  else {
    p->next = tail->next;
    tail->next = p;
  }
  head->value++;
}

Node* LinkList::FindByIndex(int index){
  Node* p = head;
  if (index < 0 || index > GetLength()){
    cout << "out of range";
    return nullptr;
  }
  int i = 0;
  while(p){
    if (i == index) return p;
    else{
      p = p->next;
      i++;
    }
  }
  return nullptr;
}

Node* LinkList::FindByValue(int value){
  Node* p = head->next;
  while (p){
    if (p->value == value) return p;
    else p = p->next;
  }
  return nullptr;
}

int LinkList::GetLength(){
  return head->value;
}

void LinkList::DeleteByIndex(int index){
  if (index == 0) return;
  Node* p = FindByIndex(index);
  if (!p) return;
  else{
    Node* q = FindByIndex(index-1);
    q->next = p->next;
    head->value--;
    delete p;
  }
}

void LinkList::DeleteByValueOnce(int value){
  Node* p = head->next;
  Node* q = head;
  bool flag = false;
  while(p){
    if (p->value == value){
      q->next = p->next;
      delete p;
      flag = true;
      head->value--;
      break;
    }
    p = p->next;
    q = q->next;
  }
  if(!flag) cout << "value is not exist in this list";
}

void LinkList::DeleteByValueAll(int value){
  Node* p = head->next;
  Node* q = head;
  bool flag = false;
  while(p){
    if (p->value == value){
      q->next = p->next;
      Node* temp = p;
      p = p->next;
      delete temp;
      head->value--;
      flag = true;
    }else{
      p = p->next;
      q = q->next;
    }
  }
  if(!flag) cout << "value is not exist in this list";
}

void LinkList::EditByIndex(int index, int value){
  Node* p = FindByIndex(index);
  if (!p) return;
  else{
    p->value = value;
  }
}


void LinkList::Print(){
  Node* p = head->next;
  while(p){ 
    cout << p->value << " ";
    p = p->next;
  }
  cout << endl;
}

void printAnswer(LinkList linklist) {
    linklist.Print();
    cout << "当前长度：";
    cout << linklist.GetLength() << endl;
}
int main() {
  int n;
  cout << "请输入节点个数：";
  cin >> n;
  LinkList linklist;
  linklist.Create();
  int num;
  while (n--) {
      cin >> num;
      linklist.InsertHead(new Node(num));
  }
  cout << "头插法结果：";
  printAnswer(linklist);
  cout << "尾插一个数：";
  cin >> num;
  linklist.InsertTail(new Node(num));
  cout << "尾插法结果：";
  printAnswer(linklist);
  cout << "想删除第几个：";
  cin >> num;
  linklist.DeleteByIndex(num);
  cout << "删除结果：";
  printAnswer(linklist);
  cout << "输入你想删除值为多少的节点(只删除首个)：";
  cin >> num;
  linklist.DeleteByValueOnce(num);
  cout << "删除结果：";
  printAnswer(linklist);
  cout << "输入你想删除值为多少的节点(所有的)：";
  cin >> num;
  linklist.DeleteByValueAll(num);
  cout << "删除结果：";
  printAnswer(linklist);
  int replace;
  cout << "输入你想修改第几个节点并改成值为多少：";
  cin >> num >> replace;
  linklist.EditByIndex(num, replace);
  cout << "修改结果：";
  printAnswer(linklist);
}