List

특징

• 일정한 순서를 가지는 요소들의 집합
• 배열은 일정 순서를 가지지 않지만 List는 일정한 순서를 유지해야함
• 선형 자료구조이며 정해지지 않은 위치에서 삽입, 삭제가 가능
  (Stack이나 Queue는 맨앞 내지는 맨뒤에서만 발생)

구성요소

Insert(int index, T item) : index위치에 입력받은 값을 추가
Delete(int index) : index위치에 입력받은 값을 제거
[int index] : index위치에 있는 값을 반환
IsEmpty() : 리스트가 비어있는지 여부를 반환
IsFull() : 리스트가 가득 차 있는지 여부를 반환
Find(T item) : 해당 요소가 리스트에 존재하는지 여부를 확인
Replace(int index, T item) : index위치에 있는 값을 새로 입력한 item으로 교체
size : 리스트가 가지고 있는 요소의 개수

구현

• 배열을 사용해 구현하는 방법이 있고 Linked List를 사용해 구현할 수 있음

Private 필드

	int 	data[MAX_LIST_SIZE];				
	int 	length; 	

• 데이터를 저장할 배열data와 현재 담고 있는 요소들의 갯수를 확인할 수 있는 length 변수 선언

insert()

	void insert( int pos, int e ) { 
		if( !isFull() && pos >= 0 && pos<=length ) {
			for( int i=length ; i>pos ; i-- )
				data[i] = data[i-1];
			data[pos] = e;
			length++;
		}
		else error("Overflow error or invalid insert position");
	}

• 입력받은 위치가 length 보다 작아야 배열 내에 추가할 수 있고, 배열이 가득 차있지 않아야 하므로 이를 먼저 확인
• 이후 끝 지점에서 pos까지 값을 1칸씩 뒤로 옮기고 pos 자리에 입력받은 값을 추가

Remove()

	void remove( int pos ) {
		if( !isEmpty() && 0<=pos && pos<length ) {
			for(int i=pos+1 ; i<length ; i++ )
				data[i-1] = data[i];
			length--;
		}
		else error("Underflow error or invalid delete position");
	}

• 배열이 비어있는지 확인하고 제거하고자 하는 위치가 배열이 값을 갖고 있는 범위 이내인지 확인
• 제거하고자 하는 위치인 pos에서 1칸 뒤에있는 값부터 앞으로 당겨 오고 전체 길이를 하나 줄여 마무리

find()

	bool find( int item ) {
		for( int i=0 ; i<length ; i++ )
			if( data[i] == item ) return true;
		return false;
	}

• 배열의 시작부터 하나씩 입력받은 값과 같은지 확인하다 같은 값을 찾았을 때 true 값을 반환

단점

• Linked List를 사용하지 않고 배열을 사용해서 List를 구현했을 때 값을 추가하거나 삭제할 때 모든 배열 내의 요소를 이동시켜야하는 번거로움이 존재
• 배열의 최대 크기만큼 큰 메모리 공간을 점유하고 있다는 단점이 존재