[Panda] 03. List 리스트

Study/[Panda] 자료구조 스터디

[Panda] 03. List 리스트

orieasy1 2024. 8. 2. 09:30

01. 리스트란

리스트는 대표적인 자료구조 중 하나로 '줄 세워져 있는 데이터' 또는 '죽 늘어선 데이터'를 의미한다.

리스트를 관리하기 위해 필요한 작업은 다음과 같을 것이다.

다음은 리스트가 어떤 작업으로 구성된 자료구조인지를 알려주는 ADT 리스트이다.

i번째 자리에 원소 x를 삽입한다.
i번째 원소를 삭제한다.
원소 x를 삭제한다.
원소 x가 몇번째 원소인지 알려준다.
리스트의 사이즈(원소의 총 수)를 알려준다.

파이썬은 리스트를 기본 자료구조로 제공하여 더 많은 작업을 지원하지만 자바는 언어 자체에서 ㅣ릇트를 기본 자료구조로 제공하지 않고 java.util 패키지에서 제공한다.

리스트의 구현

리스트를 구현하는 두 가지 대표적인 방법

배열에 원소들을 쭉 배치하는 방법
링크를 이용해 원소들을 연결하는 방법(연결 리스트)

배열을 이용한 리스트

시작 위치부터 빈자리 없이 자료를 순서대로 연속하여 저장하므로 논리적인 순서와 물리적인 순서가 일치
원소를 삽입하거나 삭제해도 빈자리 없이 자료가 순서대로 연속하여 저장된다.
가장 단순하고 효율성이 높 구현 방법, 메모리의 연속된 공간에서 데이터를 관리
이름과 크기만 정하면 되기 때문에 편리하지만 삽입될 원소의 양을 예상하여 충분한 공간을 확보해두고 작업을 시작해야하기 때문에 공간 낭비가 심하다.

연결 리스트

물리적 위치나 순서와 상관없이 링크에 의해 논리적인 순서를 표현하므로 삽입, 삭제 연산을 하여 논리적인 순서가 변경되어도 링크 정보만 변경되고 물리적인 순서는 변경되지 않는다.
동적 할당 방식을 따르기 때문에 배열의 공간 낭비를 피할 수 는 자료 구조

02. 배열 리스트

배열 리스트 객체 구조

밑에 그림에서는 임의의 리스트 객체에는 2개의 필드, 원소들이 저장되는 배열 item[] 필드와 원소의 총수를 저장하는 numItems 필드와 수행하는 작업 10개가 있다.

박스 내부에 안에 존재하는 item[]과 변수 numItems는 박수 내부에서만 사용되는 필드란 뜻이다.

박스 안팎으로 열려 있는 메서드들은 객체 바깥에서 접근할 수 있다는 뜻이다.

오픈 소스로 제공되는 배열 기반의 리스트들은 이보다 더 다양한 작업을 지원한다.

배열 리스트의 작업

원소 삽입

add(i, x): 리스트의 i번째 원소로 x를 삽입한다.
append(x): 리스트의 맨 뒤에 원소 x를 추가한다.

리스트의 i번째 원소로 x를 삽입하려면 item[i...numItems-1] 구간의 우너솓르을 오른 쪽으로 한 칸씩 시프트하고 item[i]에 원소x를 넣어야한다.

리스트의 원소가 하나 늘었으므로 numItems 값도 1 증가해야한다.

배열리스트 k번째 자리에 원소 x를 삽입하는 알고리즘은 다음과 같다.

원소 삭제

remove(i): 리스트의 i번째 원소를 삭제한다.
removeItem(x): 리스트에서 처음으로 나타나는 x를 삭제한다.

원소를 삭제할 때는 특정 위치의 원소를 삭제하게 할 수도 있고 특정 원소를 삭제하게 할 수도 있다.

해당 원소를 삭제한 뒤 좌시프트해준다.

배열 리스트의 k번째 원소를 삭제하는 알고리즘

배열 리스트에서 원소 x 삭제하는 알고리

기타 작업

get(i): 리스트의 i번째 원소를 알려준다.
set(i, x): 리스트이 i번째 원소를 x로 대체한다.
indexOf(x): 원소x가 리스트의 몇 번재 원소인지 알려준다.
len(): 리스트의 총 원소 수를 알려준다.
isEmpty(): 리스트가 빈 리스트인지 알려준다.
clear(): 리스트를 깨끗이 청소한다.

배열 리스트의 구현

제네릭 형태로 작성하면 범용성도 보장되고 강력한 타입 체크 기능도 갖출 수 있다.

원소 타입을 고정하지 말고 제네릭 형태로 작성하는 것을 추천한다.

public class ArrayList<E> implements ListInterface<E> {
	private E item[];
	private int numItems;
	private static final int DEFAULT_CAPACITY = 64;
    
	public ArrayList() {// 생성자 1
		item = (E[]) new Object [DEFAULT_CAPACITY]; 
        numItems = 0;
	}

	public ArrayList(int n) {// 생성자 2
		item = (E[]) new Object[n];
		numItems = 0; 
	}

	// [알고리즘 5-1] 구현: 배열 리스트의 k번째 자리에 원소 x 삽입하기 
    public void add(int index, Ex) {
		if (numItems >= item. length || index < 0 || index > numItems) { /* 에러처리 */ }
		else {
			for (int i = numItems - 1; i >= index; i--)
				item[i+1] = item[i];
			item[index] = x;
			numItems++;
		}
	}

	// [알고리즘 5-2] 구현: 배열 리스트의 맨 뒤에 원소 추가하기
	public void append(Ex) {
		if (numItems >= item. length) { /* 에러처리 */ }
		else {
			item[numItems++] = x;

		}
	}

	// [알고리즘 5-3] 구현: 배열 리스트의 k번째 원소 삭제하기 
    public E remove(int index) {
    	if(isEmpty() || index < 0 || index > numItems - 1)
			return null;
		else {
			E tmp = item[index];
			for (int i = index; i <= numItems - 2; i++)
				item[i] = item[i + 1];
			numItems--;
			return tmp;
        }
    }
    
    
	// [알고리즘 5-4] 구현: 배열 리스트에서 원소 X 삭제하기
	public boolean removeItem(Ex) {
		int k = 0;
		while (k < numItems && ((Comparable)item[k]).compareTo(x) != 0)
			k++;
		if (k == numItems) return false;
		else {
			for (int i = k; i <= numItems - 2; i++)
				item[i] = item[i+1];
			numItems--;
			return true;
		}
	}
    
	// [알고리즘 5-5] 구현: 리스트의 1번째 원소 알려주기
	public E get(int index) {
		if (index >= 0 && index <= numItems-1)
			return item[index];
		else return null;
	}
    
	// [알고리즘 5-6] 구현: 배열 리스트의 1번째 원소를 x로 대체하기
	public void set(int index, Ex) {
		if (index >= 0 && index <= numItems-1)
			item[index] = x;
		else { /* 에러 처리*/}
        
	// [알고리즘 5-7] 구현: 원소 x가 배열 리스트의 몇 번째 원소인지 알려주기
		private final int NOT_FOUND = -12345;
		public int indexOf(E x) {
			int i = 0;
			for (i=0; i < numItems; i++) {
            	if (((Comparable)item[i]).compareTo(x) == 0)
					return i;
			}
			return NOT_FOUND; // not exist
        }
             
	// [알고리즘 5~8(1)] 구현: 리스트의 총 원소 수 알려주기 
    	public int len() {
        	return numItems;
		}

	// [알고리즘 5-8(2)] 구현: 리스트가 비었는지 알려주기
    	public boolean isEmpty() {
			return numItems == 0;
		}
        
	// [알고리즘 5-8(3)] 구현: 리스트 깨끗이 청소하기 
    	public void clear() {
			item = (E[]) new Object[item.length];
			numItems = 0;
		}
	}
}