数据结构之链表(C++实现)

• 链表表示的是一种数据结构，跟语言没有强相关性

• 如果我们需要实现一个链表，首先最关键的就是节点，一个节点表示链表的一个数据存储点，链表是由很多个节点组成的

• 链表还需要很多线把很多节点串联在一起，可以用数组的特性串联，也可以用指针串联。

• 代码完整实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// Node Class
template <typename T>
class Node
{
public:
  T data;
  Node<T> *next;
};

template<typename T>
class LinkList
{
public:
  LinkList();
  ~LinkList();
  int CreateLinkList(int size);
  int DestroyLinkList();
  int TravalLinkList();
  int InsertLinkList(Node<T> *data, int n);
  int DeleteLinkList(int n);

  int GetLength();
  bool IsEmpty();

  Node<T> *head; // link list head
  int size;   // link list length
};

template<typename T>
LinkList<T>::LinkList()
{
  head = new Node<T>;
  T temp;
  head->data = temp;
  head->next = NULL;
  size = 0;
}

template<typename T>
LinkList<T>::~LinkList()
{
  delete head;
}

template<typename T>
int LinkList<T>::CreateLinkList(int n)
{
  if (n < 0)
  {
    cout << "error" << endl;
    return -1;
  }
  Node<T> *ptemp = NULL;
  Node<T> *pnew = NULL;

  this->size = n;
  ptemp = this->head;
  for (int i = 0; i < n; i++)
  {
    pnew = new Node<T>;
    pnew->next = NULL;
    cout << "Please input the " << i + 1 << "th node value" << endl;
    cin >> pnew->data;
    ptemp->next = pnew;
    ptemp = pnew;
  }
  cout << "linkedList create ok" << endl;

  return 0;
}

template<typename T>
int LinkList<T>::DestroyLinkList()
{
  Node<T> *ptemp;
  if (this->head == NULL)
  {
    cout << "linkedList is empty" << endl;
    return -1;
  }
  while (this->head)
  {
    ptemp = head->next;
    free(head);
    head = ptemp;
  }
  cout << "destroy linkedList ok" << endl;
  return 0;
}

template<typename T>
int LinkList<T>::TravalLinkList()
{
  Node<T> *ptemp = this->head->next;
  if (this->head == NULL)
  {
    cout << "link list is empty" << endl;
    return -1;
  }
  while (ptemp)
  {
    cout << ptemp->data << "->";
    ptemp = ptemp->next;
  }
  cout << "NULL" << endl;
  return 0;
}

template<typename T>
int LinkList<T>::InsertLinkList(Node<T> *data, int n)
{
  Node<T> *ptemp;
  if (this->head == NULL)
  {
    cout << "link list is empty" << endl;
    return -1;
  }
  if (data == NULL)
  {
    cout << "insert node is empty" << endl;
    return -1;
  }
  // header insert
  if (n < 2)
  {
    Node<T> *pnew = new Node<T>;
    pnew->data = data->data;
    pnew->next = this->head->next;
    this->head->next = pnew;
    this->size++;

    return 0;
  }
  // tail insert
  if (n > this->size)
  {
    ptemp = this->head;
    while (ptemp->next != NULL)
    {
      ptemp = ptemp->next;
    }
    Node<T> *pnew = new Node<T>;
    pnew->data = data->data;
    pnew->next = NULL;
    ptemp->next = pnew;
    this->size++;

    return 0;
  }
  // middle insert
  else
  {
    ptemp = this->head;
    for (int i = 1; i < n; i++)
    {
      ptemp = ptemp->next;
    }
    Node<T> *pnew = new Node<T>;
    pnew->data = data->data;
    pnew->next = ptemp->next;
    ptemp->next = pnew;
    this->size++;

    return 0;
  }
}

template<typename T>
int LinkList<T>::DeleteLinkList(int n)
{
  Node<T> *ptemp;
  Node<T> *ptemp2;
  if (n > this->size)
  {
    cout << "n too big" << endl;
    return -1;
  }
  // delete head node
  if (n < 2)
  {
    ptemp = this->head->next;
    this->head->next = ptemp->next;
    free(ptemp);
    this->size--;
    return 0;
  }
  // tail delete
  if (n == this->size)
  {
    ptemp = this->head;
    for (int i = 1; i < this->size; i++)
    {
      ptemp = ptemp->next;
    }
    ptemp2 = ptemp->next;
    ptemp->next = ptemp2->next;
    free(ptemp2);
    this->size--;
    return 0;
  }
  // middle delete
  else
  {
    ptemp = this->head;
    for (int i = 1; i < n; i++)
    {
      ptemp = ptemp->next;
    }
    ptemp2 = ptemp->next;
    ptemp->next = ptemp2->next;
    free(ptemp2);
    this->size--;
    return 0;
  }
  return 0;
}

template<typename T>
int LinkList<T>::GetLength()
{
  return this->size;
}

template<typename T>
bool LinkList<T>::IsEmpty()
{
  if (this->head == NULL)
  {
    return true;
  }
  else
  {
    return false;
  }
}

int main(void)
{
  cout << "Hello World!\n";
  LinkList<string> list;
  LinkList<string> *plist = &list;
  int linkListLength;
  cout << "Please input linkedList length: ";
  cin >> linkListLength;
  plist->CreateLinkList(linkListLength);
  plist->TravalLinkList();

  Node<string> temp;
  temp.data = "Hello";
  temp.next = NULL;

  plist->InsertLinkList(&temp, 0);
  plist->TravalLinkList();

  plist->InsertLinkList(&temp, plist->GetLength() + 1);
  plist->TravalLinkList();

  plist->InsertLinkList(&temp, 3);
  plist->TravalLinkList();

  plist->DeleteLinkList(0);
  plist->TravalLinkList();

  plist->DeleteLinkList(4);
  plist->TravalLinkList();

  plist->DestroyLinkList();
  system("pause");

  return 0;
}

• 效果