线性表的链式存储结构 单链表(Singly Linked List) C++

简介: 线性表的链式存储结构 单链表(Singly Linked List) C++

Node.h

#ifndef __NODE_H__
#define __NODE_H__
template <class T>
struct Node
{
  T data;
  Node<T> * next;
};
#endif


LinkedList.h

#ifndef __LINKEDLIST_H__
#define __LINKEDLIST_H__
#include "Node.h"
template <class T>
class LinkedList
{
public:
  LinkedList();
  LinkedList(T *_nodes, int _length); 
  virtual ~LinkedList();
public:
  void Insert(int _pos, T _node);
  T Delete(int _pos);
  void setNode(int _pos, T _node);
  int getLength();
  T getNode(int _pos);
  int LocateNode(T _node);
  void Traversal();
private:
  Node<T> *firstNode;
};
#endif


LinkedList.cpp

#include "LinkedList.h"
template <class T>
LinkedList<T>::LinkedList()
{
  firstNode = new Node();
  firstNode->next = nullptr;
}
template <class T>
LinkedList<T>::LinkedList(T *_nodes, int _length)
{
  firstNode = new Node<T>;
  Node<T> *tail = firstNode;
  for (int i = 0; i < _length; i++)
  {
  Node<T> *tempNode = new Node<T>;
  tempNode->data = *(_nodes + i);
  tail->next = tempNode;
  tail = tail->next;
  }
  tail->next = nullptr;
}
template <class T>
LinkedList<T>::~LinkedList()
{
  while (firstNode != nullptr)
  {
  Node<T> *deleteNode = firstNode;
  firstNode = firstNode->next;
  delete deleteNode;
  }
}
template <class T>
void LinkedList<T>::Insert(int _pos, T _node)
{
  Node<T> *tempNode = firstNode;
  Node<T> *insertNode = new Node<T>;
  for (int i = 1; i <= _pos - 1; i++)
  tempNode = tempNode->next;
  insertNode->data = _node;
  insertNode->next = tempNode->next;
  tempNode->next = insertNode;
}
template <class T>
T LinkedList<T>::Delete(int _pos)
{
  T tempdata;
  Node<T> *delNode = new Node<T>;
  Node<T> *tempNode = firstNode;
  for (int i = 1; i <= _pos - 1; i++)
  {
  tempNode = tempNode->next;
  delNode = tempNode->next;
  }
  tempNode->next = tempNode->next->next;
  tempdata = delNode->data;
  delete delNode;
  return tempdata;
}
template <class T>
void LinkedList<T>::setNode(int _pos, T _node)
{
  Node<T> *setNode = firstNode;
  for (int i = 1; i <= _pos; i++)
  setNode = setNode->next;
  setNode->data = _node;
}
template <class T>
int LinkedList<T>::getLength()
{
  int count = 0;
  Node<T> *countNode = firstNode;
  countNode = countNode->next;
  while (countNode != nullptr)
  {
  countNode = countNode->next;
  count += 1;
  }
  return count;
}
template <class T>
T LinkedList<T>::getNode(int _pos)
{
  T getData;
  Node<T> *getNode = firstNode;
  for (int i = 1; i <= _pos; i++)
  getNode = getNode->next;
  getData = getNode->data;
  return getData;
} 
template <class T>
int LinkedList<T>::LocateNode(T _Node)
{
  int locate = 0;
  Node<T> *locNode = firstNode;
  for (int i = 1; i <= this->getLength(); i++)
  {
  locate += 1;
  locNode = locNode->next;
  if (locNode->data == _Node)
    break;
  }
  return locate;
}
template <class T>
void LinkedList<T>::Traversal()
{
  Node<T> * traNode = firstNode->next;
  while (traNode != nullptr)
  {
  cout << traNode->data << " ";
  traNode = traNode->next;
  }
  cout << endl;
}


SinglyLinkedList.cpp


#include <iostream>
#include "Node.h"
#include "LinkedList.h"
#include "LinkedList.cpp"
using namespace std;
int main(void)
{
  int nodes[4] = {11, 23, 76, 45};
  LinkedList<int> *list = new LinkedList<int>(nodes, 4);
  list->Traversal();
  list->Insert(4, 0);
  list->Traversal();
  cout << list->Delete(4) << endl;
  list->Traversal();
  list->s
相关文章
|
1天前
|
存储 C++
C++的list-map链表与映射表
这篇教程介绍了C++中`list`链表和`map`映射表的基本使用。`list`链表可通过`push_front()`、`push_back()`、`pop_front()`和`pop_back()`进行元素的添加和删除,使用迭代器遍历并支持在任意位置插入或删除元素。`map`是一个键值对的集合,元素自动按键值排序,可使用下标操作符或`insert()`函数插入元素,通过迭代器遍历并修改键值对,同时提供`count()`方法统计键值出现次数。教程中包含多个示例代码以帮助理解和学习。
12 2
|
7天前
|
存储 C++
C++初阶学习第十一弹——探索STL奥秘(六)——深度刨析list的用法和核心点
C++初阶学习第十一弹——探索STL奥秘(六)——深度刨析list的用法和核心点
19 7
|
13天前
|
存储 Python
链表(Linked List)详解
链表(Linked List)详解
14 0
|
14天前
|
编译器 C语言 C++
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值(下)
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值
19 1
|
14天前
|
编译器 C语言 C++
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值(中)
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值
9 1
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值(中)
|
14天前
|
存储 安全 C语言
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值(上)
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值
13 2
|
15天前
|
C语言 容器
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器(下 )
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器
5 1
|
15天前
|
C语言 计算机视觉
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器(中)
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器
12 1
|
15天前
|
存储 算法 编译器
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器(上)
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器
11 1
|
1天前
|
存储 Java 测试技术
滚雪球学Java(57):解密Java中List接口底层实现原理
【6月更文挑战第11天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
19 2
滚雪球学Java(57):解密Java中List接口底层实现原理