鏈表

一、 何為鏈表

引用維基百科的介紹, 鏈表(Linked list)是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu), 是一種線性表, 但是并不會按照線性的順序存儲結(jié)構(gòu),是一種"在物理空間上非連續(xù)、非順序的存儲結(jié)構(gòu)"。

由于不必須按順序存儲，鏈表在插入的時候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而順序表相應(yīng)的時間復(fù)雜度分別是O(logn)和O(1)。

鏈表通常由一連串節(jié)點組成，每個節(jié)點包含:

- 鏈域：   它的值是線性表的上一個/下一個元素的位置，即地址。
- 數(shù)據(jù)域： 它的值是存儲的相應(yīng)實例數(shù)據(jù)的值。

二、鏈表的優(yōu)缺點

優(yōu)點 ：

1. 使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機(jī)內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。
2. 相比數(shù)組結(jié)構(gòu)，對于元素的插入和刪除操作來說，鏈表的效率要比數(shù)組高，因為每個節(jié)點都有鏈域存儲指向下一個節(jié)點的指針，因此進(jìn)行插入和刪除的操作時不需要頻繁的移動其他的元素，只需要修改對應(yīng)位置附近節(jié)點的鏈域的值即可。

缺點

1. 查詢鏈表只能通過指針順序訪問，效率相對低下，查詢可能需要O(n)的時間復(fù)雜度。
2. 因為鏈表的每個節(jié)點都含有鏈域，所占用的空間較多。

三、單鏈表的實現(xiàn)(C++)

• 定義節(jié)點的結(jié)構(gòu)

template<class T>
struct ListNode
{
  T m_tElement;          // 數(shù)據(jù)域
  ListNode<T>* m_pNext;  // 鏈域
  // 構(gòu)造函數(shù)
  ListNode(){}
  ListNode(const T& theElement) {this->m_tElement = theElement;}
  ListNode(const T& theElement, ListNode<T>* theNext)
  {
    this->m_tElement = theElement;
    this->m_pNext = theNext;
  }
}

• 定義鏈表類

template<class T>
class SingleList
{
public:
    // 構(gòu)造函數(shù)與析構(gòu)函數(shù)
    SingleList();
    SingleList(const SingleList<T>& theList);
    ~SingleList();
    
    // 類方法 
    bool empty() const {return m_iLength == 0;}      // 判斷鏈表是否為空
    int size() const {return m_iLength;}             // 返回鏈表長度
    int indexOf(const T& theElement) const;          
    T& get(int theIndex) const;
    void insert(int theIndex, const T& theElement);
    void delete(int theIndex);
    void update(int theIndex, const T& theElement);
    
private:
    void checkIndex(theIndex);  // 確認(rèn)是否索引值是否合法
    int m_iLength;              // 鏈表的長度
    ListNode<T>* m_pFirstNode;  // 鏈表的頭節(jié)點
}

• 構(gòu)造函數(shù)的實現(xiàn)

// 無參構(gòu)造函數(shù)
template<class T>
SingleList<T>::SingleList()
{
  m_pFirstNode = NULL;
  m_iLength = 0;
}
// 復(fù)制構(gòu)造函數(shù)
template<class T>
SingleList<T>::SingleList(const SingleList<T>& theList)
{
  m_iLength = theList.m_iLength;
  // 判斷源鏈表是否為空鏈表
  if(m_iLength == 0)
  {
    m_pFirstNode = NULL;
    return;
  }
 
  ListNode<T>* otherNode = theList.m_pFirstNode;
  m_pFirstNode = new ListNode<T>(otherNode->m_tElement);
  ListNode<T>* thisNode = m_pFirstNode;
  otherNode = otherNode->m_pNext;
  
  while (otherNode != NULL)
  { 
    // 當(dāng)源鏈表后續(xù)還有節(jié)點時，復(fù)制鏈表剩下的其他節(jié)點
    thisNode->m_pNext = new ListNode<T>(otherNode->m_tElement);
    thisNode = thisNode->m_pNext;
    otherNode = otherNode->m_pNext;
  }
  thisNode->next = NULL;
}

• 析構(gòu)函數(shù)的實現(xiàn)

template<class T>
SingleList<T>::~SingleList()
{
  while (m_pFirstNode != NULL)
  {
    ListNode<T>* tempNode = m_pFirstNode;
    delete m_pFirstNode;
    m_pFirstNode = tempNode;
  }
}

• 類方法的實現(xiàn)

  int indexOf(const T& theElement) const

// 返回指定元素的索引值
template<class T>
int SingleList<T>::indexOf(const T& theElement) const
{
  ListNode<T>* currNode = m_pFirstNode;
  int index = 0;
  while (currNode != NULL && currNode->m_tElement != theElement)
  {
    currNode = currNode->m_pNext;
    ++index;
  }
  if (currNode == NULL)
  {
    return -1;
  }
  if (currNode != NULL)
    return index;
}

? T& get(int theIndex) const

// 返回指定索引的元素
template<class T>
T& SingleList<T>::get(int theIndex) const
{
  checkIndex(theIndex);
  ListNode<T>* currNode = m_pFirstNode;
  // 找到索引值對應(yīng)的元素
  for(int i = 0; i < theIndex; ++i)
    currNode = currNode->m_pNext;
  // 返回元素的值
  return currNode->m_tElement;
}

? void insert(int theIndex, T& theElement)

// 在指定位置插入元素
template<class T>
void SingleList<T>::insert(int theIndex, const T& theElement)
{ // 判斷索引值是否合法
  checkIndex(theIndex);
  if (theIndex == 0)
  {
    m_pFirstNode = new ListNode<T>(theElement, m_pFirstNode)
  }
  if (theIndex > 0)
  {
     ListNode<T>* currNode = m_pFirstNode;
     // 因為要在指定位置插入元素, 因此去找指定位置的前一個元素
     for (int i = 0; i < theIndex - 1; ++i)
        currNode = currNode->m_pNext;
     ListNode<T>* newNode = new ListNode<T>(theElement, currNode->m_pNext);
  }
  ++m_iLength;
}

? void delete(int theIndex)

// 刪除指定位置的元素
template<class T>
void SingleList<T>::delete(int theIndex)
{
  checkIndex(theIndex);
  ListNode<T>* targetNode;
  if (theIndex == 0)
  {
    targetNode = m_pFirstNode;
    m_pFirstNode = m_pFirstNode->m_pNext;
  }
  if (theIndex > 0)
  {
    ListNode<T>* prevNode = m_pFirstNode;
    for (int i = 0; i < theIndex - 1; ++i) 
      prevNode = prevNode->m_pNext;
    targetNode = prevNode->m_pNext;
    prevNode->m_pNext = targetNode->m_pNext;
  }
  delete targetNode;
  --m_iLength;
}

? void update(int theIndex, const T& theElement)

// 修改指定位置元素的值
template<class T>
void SingleList<T>::update(int theIndex, const T& theElement)
{
  // 判斷索引值是否合法
  checkIndex(theIndex);
  // 
  if (theIndex == 0)
  {
    m_pFirstNode->m_tElement = theElement;
    return ;
  }
  
  ListNode<T>* currNode = m_pFirstNode;
  for (int i = 0; i < theIndex; ++i)
    currNode = currNode->m_pNext;
  currNode->m_tElement = theElement;
}

? void checkIndex(int theIndex)

// 檢查索引值是否合法
template<class T>
void SingleList<T>::checkIndex(int theIndex)
{
  if (theIndex < 0 || theIndex > m_iLength - 1)
    std::cout << "Error Index Value" << std::endl;
}

四、結(jié)語

這是我第一次做類似的學(xué)習(xí)筆記，借鑒了網(wǎng)上許多的博客以及書籍的資料和內(nèi)容，在這里做個記錄，若是有錯誤或不恰當(dāng)之處，希望各路大神能不吝賜教，指點小弟不足之處。