배열 기반 List (C and java)

자료구조의 첫 걸음인 배열기반 리스트를 구현해 보았다.

 

추상자료형(ADT)

-구현하고자 하는 자료구조에 대해 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열 한 것을 가리켜 추상자료형 ADT라고 한다.

특정 자료형의 내부 구현은 정확하게 알지 못해도 활용할 수 있도록 명시하는 작업이라고 생각해 볼 수 있다.

(마치 자바에서 인터페이스 혹은 추상 클래스를 정의하는 것과 비슷한 느낌이다.)

 

자료구조를 공부할 때 

1. ADT를 정의하고

2. ADT를 근거로 자료구조를 활용하는 함수를 정의하고

3. ADT를 근거로 구현하는 과정 

위 3단계 과정이 필요하다.

 

배열을 이용한 LIST 자료형의 구현

 

리스트는 간단하게 말해서 저장순서를 유지하고, 중복을 허용하여 자료를 저장하는 구조이다.

 

1. LIST자료구조의 ADT

 

1.1 구현해야할 동작

기본적인 초기화, 자료입력,조회,삭제 기능 

 

1.2 메서드 명시

void Listinit(List* plist)

-초기화 작업에 사용할 메서드이다.

-리스트 생성 후 가장 먼저 호출되어야한다.

 

void Linsert(List* plist, Ldata data)

-데이터 저장을 위한 메서드이다.

 

int LFirst(List* plist, Ldata* data)

-리스트 값의 조회를 위해 만들어진 메서드이다.

-조회에 성공하면 true, 실패하면 false를 리턴한다.

 

int Lnext(List* plist, Ldata* data)

-조회를 위해 존재한다. LFirst다음 호출되어야한다.

 

Ldata LRemove(List* plist)

-데이터 삭제를 위해 존재한다.

 

void Lclear()

-데이터 전체 삭제를 위해 존재

 

배열기반 리스트는 삭제 빼곤 크게 어려울 것이 없다.

 

출처:https://velog.io/@yyj8771/%EB%A6%AC%EC%8A%A4%ED%8A%B8-List-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

삭제하고자 하는 데이터의 인덱스의 위치가 i라고 하면, i에 해당하는 자료를 삭제하고,

i+1부터 배열의 마지막 인덱스 (배열의 length-1)까지 원래의 배열에 복사하는 과정이 필요하다.

총 복사할 갯수는 배열의 마지막 인덱스에서 삭제할 인덱스의 위치를 뺀 값일 것이다.

(배열의 length-1-i개 만큼 복사하기)

(위 자료 예시를 보면, 삭제할 인덱스 i=1 마지막 인덱스(length-1) =4 ->  3개의 자료를 기존에 복사)

for(i = rpos; i<(plist->numofdata)-1;i++){

        plist->arr[i] = plist->arr[i+1];

    }

이를 표현하면 위와 같다고 할 수 있다. 여기서 rpos는 지우고자하는 데이터의 위치이고,

plist->numofdata는 데이터의 총 갯수이므로, plist->numofdata-1은 배열의 마지막 인덱스이다.

 

 다음은 위의 내용을 C언어를 기반으로 구현한 내용이다. 

 

배열 기반 리스트 헤더

#ifndef __ARRAY_LIST_H

#define __ARRAY_LIST_H

#define false 0

#define true 1

#define MAX_LEN 100

typedef int Ldata;

typedef struct _List

{

  Ldata arr[MAX_LEN];

  int numofdata;

  int cur;

}ArrayList;

typedef ArrayList List;

void Linit(List* plist);

void Linsert(List* plist, Ldata data);

void Lclear(List* plist);

int Lfirst(List* plist, Ldata* data);

int Lnext(List* plist, Ldata* data);

Ldata Lremove(List* plist);

int size(List* plist);

#endif

배열기반 리스트 소스

#include<stdio.h>

#include "Listheader.h"

#include<stdlib.h>

void Linit(List* plist){

plist->numofdata =0;

plist->cur = -1;

}

void Linsert(List* plist, Ldata data){

  if(plist->numofdata>= MAX_LEN)

  {

    fprintf(stderr,"꽉차서 안대유");

    exit(0);

  }

    plist->arr[(plist->numofdata)++] =data;

}

int Lfirst(List* plist, Ldata* data){

    if(plist->numofdata == 0){

        fprintf(stderr,"암것두 업슈");

        return false;

    }

    plist->cur=0;

    *data = plist->arr[plist->cur];

    return true;

}

int Lnext(List* plist, Ldata* data){

    if(plist->cur >= (plist->numofdata)-1)

    {

        fprintf(stderr,"너무 갔슈");

        return false;

    }

    *data = plist->arr[++(plist->cur)];

    return true;

}

Ldata Lremove(List* plist){

    int rpos = plist->cur;

    Ldata rdata= plist->arr[rpos];

    int i;

    for(i = rpos; i<(plist->numofdata)-1;i++){

        plist->arr[i] = plist->arr[i+1];

    }

   

    (plist->numofdata)--;

    (plist->cur)--;

    return rdata;

}

int size(List* plist){

    return plist->numofdata;

}

void Lclear(List* plist){

    plist->cur = (plist->numofdata)-1;

    for(int i = (plist->numofdata)-1; i>=0;i--){

        Lremove(plist);

    }

   

}

 

다음은 JAVA로 배열기반 LIST를 구현해 보았다. 

 

MyList의 인터페이스이다. 간단하게 추가,삭제,조회 정도만 넣어두었다.

public interface MyList {

    public void Ladd(Object o);
    public boolean LhasNext();
    public Object Lnext();
    public Object Lget();
    public Object Lremove(int i);


}

다음은 MyList의 구현체 Mlist이다.

public class Mlist implements MyList{
    private Object[] obj;
    private int capacity;
    private int size=0;
    private int cur_index =-1;

    Mlist(int capacity){
        this.obj = new Object[capacity];
        this.capacity=capacity;
    }
    Mlist(){
        this(10);
    }

    @Override
    public void Ladd(Object o) {
        if(this.size == capacity)
            ensureCapacity();

        obj[size++] = o;
    }

    private void ensureCapacity() {
        this.capacity +=6;
        Object[] temp = new Object[capacity];
        System.arraycopy(obj,0,temp,0,obj.length);
        obj = temp;
    }

    @Override
    public boolean LhasNext() {
        if(size ==0){
            System.out.println("데이터가 없다");
            return false;
        }
        if(arrayindex(cur_index)) {
            cur_index =0;
            return false;
        }
        if(cur_index == -1)
            cur_index =0;


        return true;
    }

    @Override
    public Object Lnext() {
        if(cur_index >=size){
            throw new ArrayIndexOutOfBoundsException();
        }
        return obj[cur_index++];
    }

    @Override
    public Object Lget() {

        return Lget(0);
    }
    public Object Lget(int n){
        if(arrayindex(n)){
            throw new ArrayIndexOutOfBoundsException();
        }
        return obj[n];
    }

    @Override
    public Object Lremove(int i) {
        if(arrayindex(i)) throw new ArrayIndexOutOfBoundsException();
        Object Lremve = obj[i];
        try{
        System.arraycopy(obj,i+1,obj,i,size-1-i);

        }catch (ArrayIndexOutOfBoundsException e){
            ensureCapacity();
        }
        obj[size-1]=0;
        size--;
        return Lremve;
    }

    private boolean arrayindex(int i) {
        return i>=size;
    }
    public int size(){
        return this.size;
    }
    public void clear(){
        for(int i=size-1;i>=0;i--){
            Lremove(i);
        }
    }
    @Override
    public String toString(){
        String result ="[";
        for(int i=0; i<size;i++){
            result += i==0? ""+obj[i]:" "+obj[i];
        }
        return result+="]";
    }

}

 

 

JAVA에는 모든 참조변수의 포인터 역할을 할 수 있는 Object자료형이 있고,  System.arraycopy등과 같은 메서드들이 

c보다 구현하기 더 수월하였다.

c와는 다르게 배열의 크기를 보장해주는 ensurecapacity메서드나, 인덱스를 얻어서 바로바로 값을 얻을 수 있는 get메서드 등도 만들어 보았다.

 

삭제하는 메서드는 for문 대신

System.arraycopy(obj,i+1,obj,i,size-1-i);

의 형태로 바꾸었다.

 

 

 

 

참고자료

 

자바의 정석 

열혈자료구조