首页 > 代码库 > 数据结构——链表(linkedlist)

数据结构——链表(linkedlist)

基本分类:

1、单向链表

2、带尾指针的单向链表

3、双向循环链表

以下分类进行说明

1、单向链表

基本元素:*front  //头节点

     *next  //下一节点

声明:node<T>*p;

初始化:p=new node<T>(nodeValue,nextpointer);

 

简单遍历:

 1 template <typename T> 2 void writeLinkedList(node<T> *front) 3 { 4     node<T> *curr; 5     curr=front; 6     while(curr!=NULL) 7     { 8         cout<<curr->nodeValue<<" "; 9         curr=curr->next;10     }11 }

插入元素

- 插在表头:

node<T> *newnode;

newnode=new node<T>(item,front);  //使新节点的next指向头指针

front=newnode;  //使新节点成为头指针

- 插在某位置:

node<T> *prev=NULL,*curr=front;

while(curr->nodevalue!=searchItem){

  prev=curr;

  curr=curr->next;

}

newnode->next=curr;

prev->next=newnode;

 

删除元素

- 删表头

node<T> *curr=front;

front=front->next;

delete curr;

- 删某元素

node<T> *prev=NULL,*curr=front;

while(curr->nodevalue!=searchItem){

  prev=curr;

  curr=curr->next;

}

prev->next=curr->next;

delete curr;

具体代码实现:

 1 void eraseValue(node<T> *front,const T &target) 2 { 3     node<T>*curr=front,*prev=NULL; 4     bool FoundItem=false; 5     while(curr!=NULL && !FoundItem)    //未到链表末尾且未找到节点  6     { 7         if(curr->nodeValue=http://www.mamicode.com/=target) 8         { 9             if(prev==NULL)    //所删节点为头节点10                 front=front->next;11             else12                 prev->next=curr->next;13             delete curr;14             FoundItem=true; 15         }16         else17         {18             prev=curr;19             curr=curr->next;20         }21     }22 }

 

2、双指针单向链表

基本元素:*front  //头节点

     *next  //下一节点

     *end  //尾指针

 

数据结构——链表(linkedlist)