【数据结构】手搓链表

一、定义

typedef struct node_s
{int _data;struct node_s *_next;
} node_t;typedef struct list_s
{node_t *_head;node_t *_tail;
} list_t;

1. 节点结构体（node_s）：

   • int _data;存储节点中的数据
   • struct node_s *_next;：指向 node_s 类型的指针，用来指向链表中的下一个节点

2. 链表结构体（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";
}