Linked List

Linked List is a kind of #List that each individual data element (cell) points to its successor’s memory location. Usually, the last cell will be point to a null location.

With small changes of implementation, we could get two variation out of it: Double Linked List# and Circularly Linked List#.

Analysis

  • Both printing the list transversely and finding an element in the list will result in \(O(N)\) time in worse case scenario
  • Find element by using index should usually result in \(O(i)\) (i as according to index number specified) time but in worst case scenario it will result in \(O(N)\) time
  • Deleting a node from the list could result in \(O(N)\) time
  • Inserting a node to the list should result in \(O(1)\) time

Attention

  • when indirection, the pointer should not be null
  • use malloc appropriately
    • number of calls to malloc = the size of the list

Implementation

#ifndef _List_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);

#endif  // _List_H
struct Node {
  ElementType Element;
  Position    Next;
};

// Return true if L is empty
int IsEmpty(List L) {
  return L->Next == NULL;
}

/**
 *  Return true if P is the last position in list L
 *  Parameter L is unused in this implementation
 */
int IsLast(Position P, List L) {
  return P->Next == NULL;
}

// Return Position of X in L; NULL if not found
Position Find(ElementType X, List L) {
  Position P;

  P = L->Next;
  while(P != NULL && P->Element != X)
    P = P->Next;

  return P;
}

/**
 *  Delete first occurrence of X from a list
 *  Assume use of a header node
 */
void Delete(ElementType X, List L) {
  Position P, TmpCell;

  P = FindPrevious(X, L);

  if (!IsLast(P, L)) {  // Assumption of header use
                        // X is found; delete it
    TmpCell = P->Next;
    P->Next = TmpCell->Next;  // Bypass deleted cell
    free(TmpCell);
  }
}

/**
 *  If X is not found, then Next field of returned
 *  Position is NULL
 *  Assumes a header
 */
Position FindPrevious(ElementType X, List L) {
  Position P;

  P = L;
  while (P->Next != NULL && P->Next->Element != X)
    P = P->Next;

  return P;
}

/**
 *  Insert (after legal position P)
 *  Header implementation assumed
 *  Parameter L is unused in this implementation
 */
void Insert(ElementType X, List L, Position P) {
  Position TmpCell;

  TmpCell = malloc(sizeof(struct Node));
  if (TmpCell == NULL)
    FatalError("Out of space!!!");

  TmpCell->Element = X;
  TmpCell->Next = P->Next;
  P->Next = TmpCell;
}

void DeleteList(List L) {
  Position P, Tmp;

  P = L->Next;  // Header assumed
  L->Next = NULL;
  while (P != NULL)
  {
    Tmp = P->Next;
    free(P);
    P = Tmp;
  }
}
Links to this page
#data-structure #list