一、定义
typedef struct node_s
{
int _data;
struct node_s *_next;
} node_t;
typedef struct list_s
{
node_t *_head;
node_t *_tail;
} list_t;
-
节点结构体（node_s）：
int _data;存储节点中的数据struct node_s *_next;：指向node_s类型的指针，用来指向链表中的下一个节点
-
链表结构体（list_s）：
node_t *_head;：这是一个指向node_s类型的指针，用来指向链表的第一个节点，即头节点。如果链表为空，那么_head应该指向NULL。node_t *_tail;：这是一个指向node_s类型的指针，用来指向链表的最后一个节点，即尾节点。如果链表为空，那么_tail也应该指向NULL。
链表的结构图如下：
初始化：
头尾结点指针均置为空
void init(list_t *l)
{
l->_head = NULL;
l->_tail = NULL;
}二、插入
1、头插法
由于函数需要更改pHead的指向，而pHead是指向Head结点的指针类型为node_t *，所以函数需要传入pHead的地址即：node_t **二级指针，如图所示传入ppHead和ppTail
- 若链表为空，则头尾指针均指向新节点
- 若不为空，则新结点与pHead指向相同，即指向Head，再将pHead前移
void headInsert(node_t **ppHead, node_t **ppTail, int data)
{
node_t *pNew = (node_t *)malloc(sizeof(node_t));
bzero(pNew, sizeof(node_t));
pNew->_data = data;
if (*ppHead == NULL)
{
*ppHead = pNew;
*ppTail = pNew;
}
else
{
pNew->_next = *ppHead;
*ppHead = pNew;
}
}2、尾插法
参数与头插法相同
- 若链表为空，则头尾指针均指向新节点
- 若不为空，则pTail指向的Tail结点的_next指向新节点，再将pTail后移
void tailInsert(node_t **ppHead, node_t **ppTail, int data)
{
node_t *pNew = (node_t *)malloc(sizeof(node_t));
bzero(pNew, sizeof(node_t));
pNew->_data = data;
if (*ppHead == NULL)
{
*ppHead = pNew;
*ppTail = pNew;
}
else
{
(*ppTail)->_next = pNew;
*ppTail = pNew;
}
}三、遍历
void visit(node_t *pHead)
{
node_t *pCur = pHead;
while (pCur)
{
printf("%d ", (*pCur)._data);
pCur = pCur->_next;
}
printf("\n");
}四、测试
1、头插法
list_t list;
init(&list);
for (int i = 0; i < 10; i++)
{
headInsert(&list._head, &list._tail, i);
visit(list._head);
}运行结果：
2、尾插法
list_t list;
init(&list);
for (int i = 0; i < 10; i++)
{
tailInsert(&list._head, &list._tail, i);
visit(list._head);
}
return 0;运行结果：
五、使用C++对其封装
class List
{
public:
List();
~List();
void push_back(int data);
void push_front(int data);
void visit();
private:
typedef struct node_s
{
int _data;
struct node_s *_next;
} node_t;
node_t *_pHead;
node_t *_pTail;
};
List::List()
{
_pHead = nullptr;
_pTail = nullptr;
}
List::~List()
{
node_t *pCur = _pHead;
node_t *temp = nullptr;
while (pCur)
{
temp = pCur;
pCur = pCur->_next;
delete temp;
temp = nullptr;
}
}
void List::push_back(int data)
{
node_t *pNew = new node_t();
pNew->_data = data;
pNew->_next = nullptr;
if (_pHead == nullptr)
{
_pHead = pNew;
_pTail = pNew;
}
else
{
pNew->_next = _pHead;
_pHead = pNew;
}
}
void List::push_front(int data)
{
node_t *pNew = new node_t();
pNew->_data = data;
pNew->_next = nullptr;
if (_pHead == nullptr)
{
_pHead = pNew;
_pTail = pNew;
}
else
{
_pTail->_next = pNew;
_pTail = pNew;
}
}
void List::visit()
{
node_t *pCur = _pHead;
while (pCur)
{
std::cout << (*pCur)._data << " ";
pCur = pCur->_next;
}
std::cout << "\n";
}
