** 구현에 대하여
1. 의사코드의 실제 구현은 C로 하였음
2. 리스트의 원소는 문자(character)로 정하였음
3. 순회(traverse)는 출력으로 시각화하였음

리스트 ADT

연속적 임의 개체들을 모델링하는 추상자료형
= 원소들의 순서 집단을 저장하기 위한 기초적이고 일반적 목적의 데이터 구조

순위(r : rank)

• 특징 : 해당 원소 앞의 개수를 특정하는 수단
• 쓸모 : 원소(e : element)에 대한 접근 도구 (e.g. 접근, 삽입, 삭제)

메소드 개요

• 일반 메소드
  • boolean isEmpty()
  • integer size()
  • iterator elements()
• 접근 메소드
  • element get(r)
• 갱신 메소드
  • element set(r, e)
  • add(r, e)
  • addFirst(e)
  • addLast(e)
  • element remove(r)
  • element removeFirst()
  • element removeLast()

예외(exception)

• invalidRankException() : 올바르지 않은 rank가 입력된 경우
• fullListException() : 리스트에 빈 공간이 없어 명령을 수행할 수 없는 경우
• emptyListException() : 리스트에 원소가 한 개도 없어 명령을 수행할 수 없는 경우

구현 방법에 따른 시간복잡도

메소드	배열	단일연결리스트	이중연결리스트
init	O(1)	O(1)	O(1)
get / set	O(1)	O(n)	O(n)
traverse	O(n)	O(n)	O(n)
add / remove	O(n)	O(n)	O(n)
addFirst / removeFirst	O(n)	O(1)	O(1)
addLast / removeLast	O(1)	O(n)	O(1)

1차원 배열을 사용한 구현

기본 구성요소

• 배열 메모리 크기 N : 현재 최대로 담을 수 있는 원소 개수
• 리스트 크기 n : 저장된 원소 개수
• 순위 r : 0부터 시작

초기화 : O(1)

Alg init()
  input array V, integer N, integer n
  output an empty array V of size N
1. n ← 0
2. return

// 각 원소가 문자(character)를 담는다고 가정
#include<stdio.h>

void init(char** V, int N, int* n){
  *V = (char*)malloc(sizeof(char)*N);
  *n = 0;
}

int main(){
  char* V;
  int N, n;
  
  scanf("%d", &N);
  init(&V, N, &n);
  
  return 0;
}

순회 : O(n)

Alg traverse()
  input array V, integer N, integer n
  output none
1. for r←0 to n-1
     visit(V[r])
2. return

// 각 원소가 문자(character)를 담는다고 가정
// traverse의 결과가 보이도록 print기능으로 구현
void print(char *V, int n) {
  for(int r=0; r<n-1; r++){
    printf("%d ", V[r]);
  }
  printf("\n");
}

삽입

add : O(n)
addFirst : O(n)
addLast : O(1)

Alg add(r, e)
  input array V, element e, rank r, integer N, integer n, 
  output none
1. if(r<0 || r>n)
     invalidRankException()
2. if(n==N)
     fullListException()
3. for i←n-1 downto r
     V[i+1] ← V[i]
4. V[r] ← e
5. n ← n+1
6. return

char add(char *V, char e, int r, int N, int *n) {
  // 예외처리
  if( (r<0)||(r>(*n)) ){
    printf("invalid rank exception\n");
    return e;
  }
  if(*n==N){
    printf("full list exception\n");
    return e;
  }
  
  // 삽입 수행
  for(int i=*n; i>r; i--)
    V[i] = V[i-1];
    
  V[r] = e;
  *n += 1;
  
  return e;
}

삭제

remove : O(n)
removeFirst : O(n)
removeLast : O(1)

Alg remove(r)
  input array V, rank r, integer N, integer n
  output element e
1. if(r<0 || r>n-1)
     invalidRankException()
2. for i←r to n-2
     V[i] ← V[i+1]
3. n ← n-1
return

char Remove(char* V, int r, int* n) {
  if( (r<0)||(r>(*n)-1) ){
    printf("invalid rank exception\n");
    return '0';
  }
  char e = V[r];
  for(int i=r; i<(*n)-1; i++)
    V[i] = V[i+1];
  *n -= 1;
  
  return e;
}

원형 배열을 사용한 구현

기본 구성요소

원형 배열로 구현한다

• 배열 이름 V
• 배열 크기 N
• 배열의 첫 첨자 f, 마지막 첨자 l
• 리스트 크기 n
• 순위 r : 0부터 시작

size

Alg size()
1. return (N-f+l+1)%N 

get/set

Alg get(r)
1. if(r<0 || r>size()-1)
     invalieRankException()
2. return A[(f+r)%N]

Alg set(r, e)
1. if(r<0 || r>size()-1)
     invalidRankException()
2. return A[(f+r)%N]

삽입

Alg add(r, e)
1. if(r<0 || r>size())
     invalidRankException()
2. if(n==N-1)
     fullListException()
3. if(r<n/2)
     for i ← 0 to r-1
       A[(N+f+i-1)%N] ← A[(f+i)%N]
     A[(N+f+r-1)%N] ← e
     f ← (N+f-1)%N
   else
     for i ← n-1 downto r
       A[(f+i+1)%N] ← A[(f+i)%N]
     A[(f+r)%N] ← e
     l ← (l+1)%N
4. return

삭제

Alg remove(r)
1. if(r<0 || r>size()-1)
     invalidRankException()
2. if(r<n/2)
     for i ← r-1 downto 0
       A[(f+i+1)%N] ← A[(f+i)%N]
     f ← (f+1)%N
   else
     for i ← r+1 downto n-1
       A[(f+i-1)%N] ← A[(f+i)%N]
     l ← (N+l-1)%N

단일연결리스트를 사용한 구현

기본 구성요소

헤더와 트레일러가 있는 연결리스트로 구현한다.

• 연결리스트 이름 L
• 리스트 크기 n
• 순위 r : 1부터 시작

초기화 : O(1)

Alg init()
  input none
  output singly linked list L with header H, trailer T
1. H ← getNode()
2. T ← getNode()
3. H.next ← T
4. n ← 0
5. return L

#include <stdio.h>

typedef struct _Node {
  char e;
  struct _Node* next;
} Node;

Node* getNode (){
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->next = NULL;

  return newNode;
}

void putNode (Node* p){
  free(p);
}

Node* init(){
  Node* H = getNode();
  Node* T = getNode();
  H->next = T;

  return H;
}

int main(){
  Node* L = init();
  int n = 0;
  
  return 0;
}

순회 : O(n)

Alg traverse()
  input singly linked list L with header H, trailer T
  output none
1. p ← H
2. while(p != NULL)
     p ← p.next
     visit(p.elem)
3. return

void print(Node* H){
  Node* p = H->next;
  while(p->next != NULL){
    printf("%c ", p->e);
    p = p->next;
  }
  printf("\n");
}

삽입

add : O(n)
addFirst : O(1)
addLast : O(n)

Alg add(r, e)
  input L, rank r, element e, integer n
  output none
1. if( r<1 || r>n+1 )
     invalidRankException()
2. p ← H
3. for i ← 1 to r
     p ← p.next
4. addNodeBefore(p, e, r)
5. n ← n+1
6. return

Alg addNodeBefore(p, e, r)
  input L, node p, element e, rank r
  output node q
1. q ← getNode() { 새로운 노드 추가 }
2. q.elem ← e
3. q.next ← p

4. p ← H { 링크 잇기 }
5. if( r>1 )
     for i ← 1 to r-1
       p ← p.next
6. p.next ← q
7. return

char add(Node* H, int r, char e, int* n){
  if( (r<1)||(r>(*n)+1) ){
    printf("invalid rank exception\n");
    return e;
  }
  
  Node* p = H;
  for(int i=0; i<r; i++)
    p = p->next;
  addNodeBefore(H, p, r, e);
  
  *n += 1;
  return e;
}

void addNodeBefore(Node* H, Node* p, int r, char e){
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->e = e;
  newNode->next = p;

  Node* q = H;
  for(int i=0; i<r-1; i++)
    q = q->next;
  q->next = newNode;
}

삭제

remove : O(n)
removeFirst : O(1)
removeLast : O(n)

Alg remove(r)
  input L, rank r
  output none
1. if( r<1 || r>n )
     invalidRankException()
2. p ← H
3. for i ← 1 to r 
     p ← p.next
4. e ← removeNode(p)
5. n ← n-1
6. return e

Alg removeNode(p, r)
  input L, node p, rank r
  output none
1. q ← p.next 	{ 임시저장 }
2. e ← p.elem
3. putNode(p) 	{ 노드 할당풀기 }
4. p ← H 		{ 링크 잇기 }
5. if( r>1 )
     for i ← 1 to r-1
       p ← p.next
6. p.next ← q
5. return e

char Remove(Node* H, int r, int* n){
  if( (r<1)||(r>(*n)) ){
    printf("invalid rank exception\n");
    return '0';
  }

  Node* p = H;
  for(int i=0; i<r; i++)
    p = p->next;
  char e = removeNode(H, p, r);

  *n -= 1;
  return e;
}

char removeNode(Node* H, Node* p, int r){
  Node* newNext = p->next;
  char e = p->e;
  putNode(p);

  Node* q = H;
  for(int i=0; i<r-1; i++)
    q = q->next;
  q->next = newNext;
  
  return e;
}

이중연결리스트를 사용한 구현

기본 구성요소

헤더와 트레일러가 있는 이중연결리스트로 구현한다.

• 연결리스트 이름 L
• 리스트 크기 n
• 순위 r : 1부터 시작

초기화 : O(1)

Alg init()
  input none
  output doublely linked list L with header H, trailer T
1. H ← getNode()
2. T ← getNode()
3. H.next ← T
4. T.prev ← H
5. n ← 0
6. return L

#include <stdio.h>

typedef struct _Node {
  char e;
  struct _Node* prev;
  struct _Node* next;
} Node;

Node* getNode(){
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->prev = NULL;
  newNode->next = NULL;

  return newNode;
}

void putNode(Node* p){
  free(p);
}

Node* init(Node** H, Node** T){
  *H = getNode();
  *T = getNode();
  (*H)->next = *T;
  (*T)->prev = *H;

  return *H;
}

int main(){
  Node* H; // Head
  Node* T; // Trailer
  Node* L = init(&H, &T);
  int n = 0;

  /*
  add(L, 1, 'a', &n);
  add(L, 2, 'b', &n);
  addLast(T, 'f', &n);
  print(L); // a b f

  Remove(L, 1, &n);
  RemoveLast(T, &n);
  print(L); // b

  set(L, 1, 'z', n); // z
  printf("%c\n", get(L, 1, n)); // z
  */
  
  return 0;
}

순회 : O(n)

Alg traverse()
  input list L
  output none
1. p ← H.next
2. while(p!=T)
     visit(p.elem)
     p ← p.next
3. return

void print(Node* H){
  Node* p = H->next;
  while(p->next != NULL){
    printf("%c ", p->e);
    p = p->next;
  }
  printf("\n");
}

get/set : O(n)

Alg get()
  input list L, rank r
  output element e
1. if( r<1 || r>n )
     invalidRankException()
2. p ← H.next
3. for i ← 1 to r-1
     p ← p.next
4. return p.elem

Alg set()
  input list L, rank r, new element e
  output element e
1. if( r<1 || r>n )
     invalidRankException()
2. p ← H.next
3. for i ← 1 to r-1
     p ← p.next
4. p.elem ← e
5. return p.elem

char get(Node* H, int r, int n){
  if( (r<1)||(r>(n)) ){
    printf("invalid rank exception\n");
    return '0';
  }
  
  Node* p = H->next;
  for(int i=0; i<r-1; i++)
    p = p->next;

  return p->e;
}

char set(Node* H, int r, char e, int n){
  if( (r<1)||(r>(n)) ){
    printf("invalid rank exception\n");
    return '0';
  }
  
  Node* p = H->next;
  for(int i=0; i<r-1; i++)
    p = p->next;
  p->e = e;
  
  return p->e;
}

삽입

add : O(n)
addFirst : O(1)
addLast : O(1)

Alg add()
  input list L, rank r, element e
  output none
1. if( r<1 || r>n+1 )
     invalidRankException()
2. p ← H.next
3. for i ← 1 to r-1
     p ← p.next
4. addNodeBefore(p, e)
5. n ← n+1
6. return

Alg addLast()
  input list trailer T, element e
  output none
1. addNodeBefore(T, e)
2. n ← n+1
3. return

Alg addNodeBefore(p, e)
  input list L, node p, element e
  output none
1. q ← getNode()
2. q.elem ← e
3. q.next ← p
4. q.prev ← p.prev
5. (p.prev).next ← q
6. p.prev ← q
7. return

char add(Node* H, int r, char e, int* n){
  if( (r<1)||(r>(*n)+1) ){
    printf("invalid rank exception\n");
    return '0';
  }
  
  Node* p = H->next;
  for(int i=0; i<r-1; i++)
    p = p->next;
  addNodeBefore(p, e);

  *n += 1;
  return e;
}

char addLast(Node* T, char e, int* n){
  addNodeBefore(T, e);
  *n += 1;
  return e;
}

void addNodeBefore(Node* p, char e){
  Node* newNode = getNode();
  newNode->e = e;
  newNode->next = p;
  newNode->prev = p->prev;

  (p->prev)->next = newNode;
  p->prev = newNode;
}

삭제

remove : O(n)
removeFist : O(1)
removeLast : O(1)

Alg remove()
  input list L, rank r
  output element e
1. if( r<1 || r>n )
     invalidRankException()
2. p ← H.next
3. for i ← 1 to r-1
     p ← p.next
4. e ← removeNode(p)
5. n ← n-1
6. return e

Alg removeLast()
  input list trailer T
  output element e
1. e ← removeNode(T.prev)
2. n ← n-1
3. return e

Alg removeNode()
  input list L, node p
  output element e
1. e ← p.elem
2. (p.prev).next ← p.next
3. (p.next).prev ← p.prev
4. putNode(p)
5. return e

char Remove(Node* H, int r, int* n){
  if( (r<1)||(r>(*n)) ){
    printf("invalid rank exception\n");
    return '0';
  } 

  Node* p = H->next;
  for(int i=0; i<r-1; i++)
    p = p->next;
  char e = RemoveNode(p);

  *n -= 1;
  return e;
}

char RemoveLast(Node* T, int* n){
  char e = RemoveNode(T->prev);
  *n -= 1;
  return e;
}

char RemoveNode(Node* p){
  char e = p->e;
  (p->prev)->next = p->next;
  (p->next)->prev = p->prev;
  putNode(p);

  return e;
}