存盤結構：
陣列是一塊連續的記憶體空間存盤的，然而鏈表是零散的記憶體空間存盤的，
鏈表在插入和洗掉操作比陣列高效，時間復雜度僅為O(1)，鏈表不是使用連續的記憶體空間，所以可以充分利用零散的記憶體空間，
鏈表結構：
1. 單向鏈表
2. 雙向鏈表
現在最常見的鏈表結構：
單向鏈表、雙向鏈表，下面說一下這幾種鏈表結構的實際操作
1. 單向鏈表
單向鏈表插入：找到節點a，在a節點插入節點x，先將x->next指向下一個節點a->next(c節點)，再將a->next指向節點x，這里有一個點需要注意，不能先將a->next指向節點x，這樣會丟掉節點c的，
單向鏈表洗掉：找到節點b前一個節點a，將a->next指向b->next(c節點)
單向鏈表查找：一個一個節點往下找
實作代碼：
template<class T> struct ListNode { T data; ListNode<T>* pNext; ListNode() { pNext = NULL; } }; template<class T> class MyList { public: MyList(); ~MyList(); void InsertListNode(T const& ,int const&); void DeleteListNode(int const&); void ReverseList(); int SeachListNode(T const&) const; int GetListSize() const; ListNode<T>* GetListHeadNode() const; protected: ListNode<T> *pHead; private: }; template<class T> MyList<T>::MyList() { pHead = NULL; } template<class T> MyList<T>::~MyList() { while(pHead != NULL) { ListNode<T>* pTmp = pHead; pHead = pHead->pNext; delete pHead; } } template<class T> void MyList<T>::InsertListNode(T const& param, int const& nPosition) { if(nPosition > GetListSize() + 1) { return ; } ListNode<T>* pInsertNode = new ListNode<T>; pInsertNode->data =https://www.cnblogs.com/yew0/p/ param; pInsertNode->pNext = NULL; //List empty if(pHead == NULL) { pHead = pInsertNode; return ; } int nP = nPosition; ListNode<T>* pCurrent = pHead; while(nP>1 && pCurrent->pNext != NULL) { pCurrent = pCurrent->pNext; nP--; } pInsertNode->pNext = pCurrent->pNext; pCurrent->pNext = pInsertNode; } template<class T> void MyList<T>::DeleteListNode(int const& nPosition) { if(pHead == NULL || nPosition > GetListSize()) { return ; } if(nPosition == 1) { ListNode<T>* pTmp = pHead; pHead = pHead->pNext; delete pTmp; return ; } int nP = nPosition; ListNode<T>* pLast = pHead; while(nP>2 && pLast->pNext != NULL) { pLast = pLast->pNext; nP--; } ListNode<T>* pCurrent = pLast->pNext; if(pCurrent != NULL) { pLast->pNext = pCurrent->pNext; } delete pCurrent; } template<class T> int MyList<T>::SeachListNode(T const& param) const { int nPostion = 0; ListNode<T>* pTmp = pHead; while(pTmp) { nPostion++; if(pTmp->data =https://www.cnblogs.com/yew0/p/= param) { return nPostion; } pTmp = pTmp->pNext; } return -1; } template<class T> int MyList<T>::GetListSize() const { int nSize = 0; ListNode<T>* pTmp = pHead; while(pTmp != NULL) { nSize++; pTmp = pTmp->pNext; } return nSize; } template<class T> ListNode<T>* MyList<T>::GetListHeadNode() const{ return pHead; }View Code
2.雙向鏈表
雙向鏈表插入：找到節點a，在a節點插入節點x，先將x->next指向下一個節點a->next(b節點)，x->prior指向節點a，b->prior指向節點x
雙向鏈表洗掉：找到節點b，b->prior(節點a)->next指向b->next(節點c)，b->next(節點c)->prior指向b->prior(節點a)
雙向鏈表查找:一個一個節點往下找
實作代碼：
template<class T> struct DoubleListNode { T data; DoubleListNode<T>* pNext; DoubleListNode<T>* pPrior; DoubleListNode() { pNext = NULL; pPrior = NULL; } }; template<class T> class DoubleList { public: DoubleList(); ~DoubleList(); void InsertDoubleListNode(T const& ,int const&); void DeleteDoubleListNode(int const&); void ReverseDoubleList(); int SeachDoubleListNode(T const&) const; int GetDoubleListSize() const; DoubleListNode<T>* GetDoubleListHeadNode() const; protected: DoubleListNode<T>* m_pHead; private: }; template<class T> DoubleList<T>::DoubleList() { m_pHead = NULL; } template<class T> DoubleList<T>::~DoubleList() { while(m_pHead != NULL) { DoubleListNode<T>* pTmp = m_pHead; m_pHead = m_pHead->pNext; delete pTmp; } } template<class T> void DoubleList<T>::InsertDoubleListNode(T const& param, int const& nPosition) { if(nPosition > GetDoubleListSize() + 1) { return ; } DoubleListNode<T>* pInsertNode = new DoubleListNode<T>; pInsertNode->data =https://www.cnblogs.com/yew0/p/ param; pInsertNode->pNext = NULL; pInsertNode->pPrior = NULL; if(m_pHead == NULL) { m_pHead = pInsertNode; return ; } int nP = nPosition; DoubleListNode<T>* pCurrent = m_pHead; while(nP>1 && pCurrent->pNext != NULL) { pCurrent = pCurrent->pNext; nP--; } pInsertNode->pNext = pCurrent->pNext; if(pCurrent->pNext) { pCurrent->pNext->pPrior = pInsertNode; } pCurrent->pNext = pInsertNode; pInsertNode->pPrior = pCurrent; } template<class T> void DoubleList<T>::DeleteDoubleListNode(int const& nPosition) { if(m_pHead == NULL || nPosition > GetDoubleListSize()) { return ; } if(nPosition == 1) { DoubleListNode<T>* pTmp = m_pHead; m_pHead = m_pHead->pNext; m_pHead->pPrior = NULL; delete pTmp; return ; } int nP = nPosition; DoubleListNode<T>* pCurrent = m_pHead; while(nP>1 && pCurrent != NULL) { pCurrent = pCurrent->pNext; nP--; } if(pCurrent != NULL) { DoubleListNode<T>* pLast = pCurrent->pPrior; pLast->pNext = pCurrent->pNext; pCurrent->pNext->pPrior = pLast; } delete pCurrent; } template<class T> int DoubleList<T>::SeachDoubleListNode(T const& param) const { int nPostion = 0; DoubleListNode<T>* pTmp = m_pHead; while(pTmp) { nPostion++; if(pTmp->data =https://www.cnblogs.com/yew0/p/= param) { return nPostion; } pTmp = pTmp->pNext; } return -1; } template<class T> int DoubleList<T>::GetDoubleListSize() const { int nSize = 0; DoubleListNode<T>* pTmp = m_pHead; while(pTmp != NULL) { nSize++; pTmp = pTmp->pNext; } return nSize; } template<class T> DoubleListNode<T>* DoubleList<T>::GetDoubleListHeadNode() const { return m_pHead; }View Code
可關注公眾號了解更多的面試技巧
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/136679.html
標籤：其他
上一篇：C++動態規劃求解0-1背包問題