[Data Structure] 리스트(List)

List

• A linear collection of storing elements of the same types.
• May have duplicate elements
• Implemented as either an array or a linked list.
• Operations
  • InitList: Make a list empty.
  • IsEmpty: Check whether the list is empty.
  • IsFull: Check whether the list is full.
  • Insertion: Insert an item at the specific position.
    • InsertFirst: Insert an item at the first position.
    • InsertLast: Insert an item at the last position.
    • InsertMiddle: Insert an item at the k-th position.
  • Deletion: Remove an item at the specific position.
    • DeleteFirst: Remove an item at the first position.
    • DeleteLast: Remove an item at the last position.
    • DeleteMiddle: Remove an item at the k-th position.
  • Retrieval: Read or replace an item at the k-th position.
  • Traversal: Read each item in a list in sequence.

ArrayList

// ArrayList
#define MAX_LIST 100

typedef enum {false, true} bool;
typedef int Data;

typedef struct{
	Data items[MAX_LIST];
    int len;
}ArrayList;

void InitList(ArrayList* plist);
bool IsEmpty(ArrayList* plist);
bool IsFull(ArrayList* plist);
void InsertMiddle(ArrayList* plist, int pos, Data item);
void RemoveMiddle(ArrayList* plist, int pos);
Data ReadItem(ArrayList* plist, int pos);
void PrintList(ArrayList* plist);

void InitList(ArrayList* plist){
	plist->len = 0;
}

bool IsEmpty(ArrayList* plist){
	return plist->len == 0;
}

bool IsFull(ArrayList* plist){
	return plist->len == MAX_LIST;
}

void InsertMiddle(ArrayList* plist, int pos, Data item){
	if(IsFUll(plist) || pos < 0 || pos > plist->len)
    	exit(1);
    for (int i = plist->len-1; i >= pos; i--)
    	plist->items[i+1] = plist->items[i];
    plist->items[pos] = item;
}

void RemoveMiddle(ArrayList* plist, int pos){
	if(IsEmpty(plist) || pos < 0 || pos >= plist->len)
    	exit(1);
    for (int i = pos; i < plist->len; i++)
    	plist->items[i] = plist->items[i+1];
    plist->len--;
}

Data ReadItem(ArrayList* plist, int pos){
	if (IsEmpty(plsit) || pos <0 || pos >= plist->len)
    	exit(1);
    return plist->items[pos];
}

void PrintList(ArrayList* plist){
	for(int i = 0; i < plist->len; i++)
    	printf("%d\n", plist->items[i]);
}

Weaknesses of ArrayList

• Pre-defined size: The maximum size should be predictable.
• Insertion & deletion are time-consuming: Require O(n) time complexity.

 

Linked List

• A linear collection of elements, called nodes, each pointing to the next node.
  • variable size, easy to change the size while running
  • Easy insertions and deletions
• Each node consist of an item with link(hook)
• Box: an item value
• Arrow: a pointer to the next box
  • If the arrow does not refer to other nodes, it is a NULL pointer.

// Linked List
typedef enum {false, true} bool;
typedef int Data;

typedef struct _Node{
	Data item;
    struct _Node* next;
}Node;

typedef struct{
	Node* head;
    int len;
}LinkedList;

void InitList(LinkedList* plist);
bool IsEmpty(LinkedList* plist);
void InsertMiddle(LinkedList* plist, int pos, Data item);
void RemoveMiddle(LinkedList* plist, int pos);
Data ReadItem(LinkedLIst* plist, int pos);
void PrintList(LinkedList* plist);
void ClearList(LinkedList* plist);

void InitList(LinkedList* plist){
	plist->head = (Node *)malloc(sizeof(Node));
    plist->head->next = NULL;
    plist->len = 0;
}

bool IsEmpty(LinkedList* plist){
	return plist->len == 0;
}

void InsertMiddle(LinkedList* plist, int pos, Data item){
	Node* cur, *newNode;
    if (pos < 0 || pos > plist->len)
    	exit(1)
    newNode = (Node *)malloc(sizeof(Node));
    newNode->item = item;
    newNode->next = NULL;
    cur = plist->head;
    
    for(int i = 0; i < pos; i++)
    	cur = cur->next
    newNode->next = cur->next
    cur->next = newNode;
    plist->len++;
}

void RemoveMiddle(Linked* plist, int pos){
	Node* cur, *temp;
    if(IsEmpty(plist) || pos < 0 || pos >= plist->len)
    	exit(1);
    cur = plist->head;
    for (int i = 0; i < pos; i++)
    	cur = cur->next;
    temp = cur->next;
    cur->next = cur->next->next;
    plist->len--;
    free(temp)
}

Data ReadItem(LinkedList* plist, int pos)
{
	Node* cur;
    if(IsEmpty(plist) || pos < 0 || pos >= plist->len)
    	exit(1);
    cur = plist->head->next;
    for (int i = 0; i < pos; i++)
    	cur = cur->next;
    reutrn cur->item;
}

void PrintList(LinkedList* plist){
	for(Node* cur = plist->head->next; cur != NULL; cur = cur->next)
    	printf("%d\n", cur->item);
}

void ClearList(LinkedList* plist){
	while(plist->head->next != NULL)
    	RemoveFirst(plist);
    free(plist->head)
}

 

Circular Linked List

• The last node is linked to the first node.
• All nodes are continuously linked in a circle.
• Advantages:
  • Useful for implementation of queue.
  • Fast insertion for the front and the back positions.
  • Any node can be a head point.

 

Double Linked List

• Each node is linked to the previous and next nodes.
• Advantages:
  • It can traverse in both directions from the front and from the end.
  • Easy to reverse the linked list
• Disadvantages:
  • Compared to the single linked list, it requires more space per node because one extra field is needed.