鏈結串列(Linked List)
單向鏈結串列(Single Linked List)
- 單向鏈結串列(Single Linked List)
-
- 由一組節點(Node)組成的有序串列
- 每個節點由資料欄和一個鏈結欄(Link, Point)組成
- 鏈結欄指向其它Node的位址
- 首結點:第一個Node
- 回收串列的時間為O(n),n為結點數
-
- Operations
- Create List:建立串列
- 建立一個空的鏈結串列 建立首節點
struct Node { int data; Node *next; }; Node *first; //宣告首節點 first = new Node; //實體化首節點 first->next = 0; //指向null first->data = -1;
struct Node { int data; struct Node *next; }; struct Node *first = NULL ; first = malloc( sizeof(struct Node) ); first->next = 0; //null pointer first->data = -1;
int Fibonacci(int n) { if( n <= 1 ) return n; int fa = 0, fb = 1, fn; for(int i = 0; i <= n; i++){ fn = fa + fb; fa = fb; fb = fn; } return fi; }
class Node { public int data; public Node next; } Node first = new Node();
- Insert Node:插入節點
- 可分為:
- 前端插入(insertFront):將新節點插入到串列最前端,並取代首節點
- 中間插入(insert):將新節點插入到指定點後面
- 尾端插入(append):將新節點插入到串列最尾端
struct Node** insert(Node **first, Node *ptrBeforeNode, int data) { Node* newNode = new Node; newNode->data = data; newNode->next = NULL; if(ptrBeforeNode == NULL){ // 插入在首節點之前 newNode->next = *first; *first = newNode; }else{ if(ptrBeforeNode->next == NULL) // 插入在尾節點之後 ptrBeforeNode->next = newNode; else{ // 插入在指定節點之後 newNode->next = ptrBeforeNode->next; ptrBeforeNode->next = newNode; } } } insert(&first, NULL, 10);
Node *createNode(void) { Node *tmpNode; tmpNode = (Node *) malloc(sizeof(Node)); if(tmpNode == NULL){ printf("記憶體不足"); exit(1); } return (tmpNode); } void insert(Node *first, Node x){ Node tmp; MALLOC(tmp, sizeof(*tmp)); tmp->data = 50; if(*first){ tmp->link = x->link; x->link = tmp; }else{ tmp->link = NULL; *first = tmp; } } Node *insertNode( Node *first, Node *theNode, int data)}{ Node *newNode; newNode = createNode(); newNode = data; newNode->link = NULL; if( theNode == NULL ){ //前端插入 newNode->link = first; first = new;Node; }else{ if(theNode->link == NULL) //尾端插入 theNode->link = newNode; else{ //中間插入 newNode->link = theNode->link; theNode->link = newNode; } } return (first); }
public void insertFront() { Node newNode = new Node(); newNode.link = first.link; first.link = newNode; }
- 可分為:
- Find Node:尋找節點
- 自指定節點開始往後依序循找符合的節點
//搜尋指定節點 struct Node* searchNode(struct Node *first, int searchData) { Node *curNode = first; while(curNode) { if(curNode->data == searchData) return curNode; curNode = curNode->next; } cout << "Not Find " + searchData << endl; }
Node findNode(Node *head, int data){ Node *node; node = first; //由首節點開始搜尋 while( node != NULL ){ //走訪串列 if( node->data == data ) //若找到,則回傳 return node; node = node->link; //指向下一個節點 } return node; } /* 計算指定節點之後的長度 */ int length( Node theNode ){ int nodeNum = 0; Node *nextNode = theNode->link; while(nextNode != NULL) { nodeNum ++; nextNode = nextNode->link; } return (nodeNum); }
- Delete Node:刪除節點
- 邏輯性移除(Logically Remove):
- 將要刪除的Node指標斷掉,無法透過鏈結串列找到該Node
- 實際移除(Physically Delete):
- 實際移除(Physically Delete):要刪除的Node從記憶體中移除
bool deleteNode(struct Node **first, Node *ptrDelNode){ Node *curNode = *first; if(ptrDelNode == *first){ //如果是首節點 *first = curNode->next; delete ptrDelNode; return true; } while(curNode){ //如果不是首節點 if(curNode->next == ptrDelNode){ curNode->next = ptrDelNode->next; delete ptrDelNode; return true; } curNode = curNode->next; } return false; }
void *freeNode(Node *tmpNode){ free(tmpNode); }
- 邏輯性移除(Logically Remove):
- Reverse Linked List:串列反轉
- 將串列節點的順序顛倒
struct Node* reverse(struct Node** List){ Node *parentNode = *List; Node *curNode = parentNode->next; Node *childNode = curNode->next; parentNode->next = NULL; while(childNode) { curNode->next = parentNode; parentNode = curNode; curNode = childNode; childNode = childNode->next; } curNode->next = parentNode; *List = curNode; return *List; }
- Copy Linked List:複製串列
- 將指定的串列複製到新的串列
void copyLinkedList(struct Node *node, struct Node **ptrNewFirstNode) { if(node != NULL) { //若要複製的串列不為空串列 *ptrNewFirstNode = new Node; (*ptrNewFirstNode)->data = node->data; (*ptrNewFirstNode)->next = NULL; copyLinkedList(node->next, &((*ptrNewFirstNode)->next)); } }
- Compare Linked List:串列比較
- 比較指定的2個串列
int compareLinkedList(struct Node *node1, struct Node *node2) { static int flag; if(node1 == NULL && node2 == NULL) { flag = 1; } else { if(node1 == NULL || node2 == NULL) flag = 0; else if(node1->data != node2->data) flag = 0; else compareLinkedList(node1->next, node2->next); } return flag; }
- Delete Linked List:刪除串列
- 刪除指定的串列
void deleteLinkedList(struct Node **node) { struct Node *tmpNode; while(*node) { tmpNode = *node; *node = tmpNode->next; delete tmpNode; } }
- Linked List Length:取得串列長度
- 計算指定串列的長度
int length(struct Node *startNode){ int num = 0; while(startNode != NULL){ num++; startNode = startNode->next; } return num; }
- Release List:回收串列
- 為避免解構Node的浪費,可用一個List(Available List)存放已不使用的Node
- 刪除Node或List時,將Node移到AV,而不真正的Delete(邏輯性移除)
- 插入Node時,由AV中取出一個Node來插入,AV中沒有Node再用New
- Display Linked List :顯示串列的內容
- 顯示串列的內容
void display(struct Node *first) { Node *list = first; while(list) { cout << list->data << " "; list = list->next; } cout << endl; }
- Create List:建立串列