Data Structure - LIST

• Also known as linked list
• The linked list is a data space in which data can be added and deleted whenever necessary, without a space of a fixed size.
• Linked list is a data structure that connects data that exist in a remote place with pointer.

Basic term

• Node - Consists of data storage units (data values, pointers)
• Pointer - In each node, a space containing connection information (address) with the next or previous node, null value if there is no next node

#include <iostream>

using namespace std;

// Single linked list
struct SNode {
  int value;
  SNode* prev;
};
SNode* sList;

void addSList(int val) {
  SNode* newNode = new SNode;
  newNode->value = val;
  newNode->prev = sList;
  sList = newNode;
}
void printSList() {
  for (SNode* iter = sList; iter != nullptr; iter = iter->prev) {
    cout << iter->value << " ";

  }
  cout << "\n";
}

// Double linked list
struct DNode {
  int value;
  DNode* prev;
  DNode* next;
};
DNode* head;
DNode* tail;

void addDList(int val) {
  DNode* newNode = new DNode();
  newNode->value = val;
  newNode->next = tail;
  newNode->prev = tail->prev;

  tail->prev->next = newNode;
  tail->prev = newNode;
}
void deletaDList(int val) {
  for (DNode* iter = head->next; iter != tail; iter = iter->next) {
    if (iter->value == val) {
      iter->prev->next = iter->next;
      iter->next->prev = iter->prev;
      delete iter;
      break;
    }
  }
}
void printDList() {
  for (DNode* iter = head->next; iter != tail; iter = iter->next) {
    cout << iter->value << " ";
  }
  cout << "\n";
}

int main() {
  // SLL
  sList = nullptr;
  addSList(100);
  addSList(200);
  printSList();

  // DLL
  head = new DNode();
  tail = new DNode();
  head->prev = nullptr;
  head->next = tail;
  tail->prev = head;
  tail->next = nullptr;

  addDList(10);
  addDList(20);

  printDList();
  deletaDList(10);
  printDList();

  return 0;
}