kenics.net

Technical notes on perl, python, php, sql, cgi, c/c++, q/kdb+, unix/shell, revision control tools, data structures & algorithms, and their applications into web services and other various forms of software engineering.

Linked List – data strcuture

 
############################## 
###    Linked List (LL)    ### 
############################## 
 
this is better explained in comparison with array. 
essentially, linked list is a list of data nodes that are linked via pointers. 
unlike array, mem allocation does not have to be contiguous. 
 
LL can be uni-directional or bi-directional. 
if you connect the last node back to the head node, then it's what we call a circular LL, or depending on the context, more commonly known as a "ring buffer". 
 
for bi-directional, each node should additionally have a pointer to a prev node. 
 
 
(ref) 
http://www.bogotobogo.com/cplusplus/linkedlist.php 
 
 
################################ 
###   array VS linked list   ### 
################################ 
 
- array is all fixed-size contiguous mem space while LL gets mem alloc from diff areas of heap. 
- array is suitable for random access via index, whereas LL requires traversal 
- insert/delete/resize in the middle of an array is expensive as you have to shift things but LL is just create a new node and change the pointers. 
- pointer in each node of LL is overhead (in 32-bit IA32 platform, it's 4byte) 
 
 
 
STL vector<T> is a wrapper to a classic array. 
 
 
########################################## 
###    Implementation example (C++)    ### 
########################################## 
 
Lets define a node. 
 
-------------------- 
struct node{ 
  struct node* next; 
  int data; 
}; 
-------------------- 
 
Now, in C, to avoid writing struct everywhere, we had to use typedef, but in C++, it's no longer needed. 
 
------------------- 
typedef struct{ 
  node* next; 
  int data; 
} node; 
------------------- 
 
 
--------------------------------------- // kll.h 
 
#include <iostream> 
#include <stdlib.h> 
using namespace std; 
 
template<typename N> struct node{ 
  struct node* next; 
  N data; 
}; 
 
template<typename T> class LL 

public: 
  LL(): head(0){;} 
  void add(T); 
  bool search(T); 
  void del(T); 
  void delAll(); 
  int sizeLL(); 
  void printLL(); 
private: 
  node<T>* head; 
}; 
 
template<typename T> void LL<T>::add(T t)                  // add to the tail. this func might as well be named append(). 

  node<T>* new_node = new node<T>(); 
//node<T>* new_node = new node<T>;   // this is ok also. 
  new_node->data = t; 
  new_node->next = 0; 
 
  if(!head){ 
    head = new_node; 
    return; 
  } 
 
  node<T>* tmp = head; 
  while(1){ 
    if(!(tmp->next)) 
      break; 
    tmp = tmp->next; 
  } 
  tmp->next = new_node; 

 
template<typename T> bool LL<T>::search(T t) 

  if(!head) 
    return false; 
  node<T>* tmp = head; 
  while(1){ 
    if(tmp->data == t) 
      return true; 
    if(!(tmp->next)) 
      break; 
    tmp = tmp->next; 
  } 

 
template<typename T> void LL<T>::del(T t)       // t = data you wanna search and delete if existent 
{                                               // ideally you should leverage the separately implemented search() 
  if(!head) 
    return; 
  else{ 
    node<T>* tmp = head; 
    node<T>* prev = head; 
    node<T>* p = head; 
 
    while(1){ 
      if(tmp->data == t){ 
        p = tmp; 
        tmp = tmp->next; 
        if(p == head)           // when deleting a head node, 
          head = head ->next;   // gotta adjust it. 
        else 
          prev->next = tmp;     // otherwise, prev->next manipulation should do it. 
        free(p); 
        break; 
      } 
      if(!(tmp->next)) 
        break; 
      prev = tmp; 
      tmp = tmp->next; 
    } 
  } 

 
template<typename T> void LL<T>::delAll() 

  if(!head) 
    return; 
  else{ 
    node<T>* tmp = head; 
    head = head->next; 
    free(tmp); 
    delAll(); 
  } 

 
template<typename T> int LL<T>::sizeLL() 

  int size=0; 
  if(!head) 
    return size; 
  size++; 
  node<T>* tmp = head; 
  while(1){ 
    if(!(tmp->next)) 
      return size; 
    size++; 
    tmp = tmp->next; 
  } 

 
template<typename T> void LL<T>::printLL() 

  cout << "-- pringint a LL of size " << sizeLL() << endl; 
 
  node<T>* tmp = head; 
  if(!tmp) 
    return; 
  while(1){ 
    cout << tmp->data << endl; 
    if(!(tmp->next)) 
      break; 
    tmp = tmp->next; 
  } 
 
  cout << "----------------" << endl; 

 
 
--------------------------------------- // main.cpp 
 
 
#include <iostream> 
#include "kll.h" 
using namespace std; 
 
int main() 

  LL<int> ll; 
 
  ll.add(123); 
  ll.add(456); 
  ll.add(789); 
  ll.add(8888); 
  ll.add(7777); 
  ll.add(555); 
 
  ll.printLL(); 
 
  if(ll.search(789)) 
    cout << "hit 789" << endl; 
  if(ll.search(999)) 
    cout << "hit 999" << endl; 
 
  ll.del(123);   // delete the head node 
 
  ll.printLL(); 
 
  ll.del(8888);  // delete an in-the-middle node 
 
  ll.printLL(); 
 
  ll.del(555);   // delete the tail node 
 
  ll.delAll(); 
 
  ll.printLL(); 
 
 
  return 0; 

 
 
--------------------------------------- 
 
 
 

  1. 2014-06-04 00:53:17 |
  2. Category : data_structure
  3. Page View:

Google Ads