[2020-1/자료구조] Lists

 

리스트(Lists)

개념

• 유한, 순서가 있는 데이터들의 나열
• 리스트 속 데이터들은 위치가 있음
• 표기법: <a_0, a_1, ... , a_n-1>

 

리스트에 필요한 연산 (리스트 ADT)

public interface List<E> {
	public void clear(); //리스트 비우기
	public void insert(int pos, E item); //특정 위치에 아이템 넣기
	public void append(int pos, E item);
	public void update(int pos, E item); //특정 위치의 아이템 변경
	public E getvalue(int pos); //특정 위치의 아이템 읽기
	public E remove(int pos); //특정 위치의 아이템 삭제
	public int length(); //리스트 내의 아이템 개수
}

 

 

 

---

 

 

ArrayList (배열 기반 리스트)

장단점

장점

• 특정 위치의 데이터 조회가 빠름

단점

• 데이터의 추가, 삭제 비용이 큼
• 크기가 고정되어 있음

 

구현

public class ArrayList<E> implements List<E> {
	
	private static final int defaultSize = 10;
	private int listSize;
	private E[] data;
	
	public ArrayList() {
		this(defaultSize);
	}
	
	public ArrayList (int size) {
		listSize = 0;
		data = (E[]) new Object[size];
	}
	
	
	public void clear() { listSize = 0; }
	public void update(int pos, E item) { data[pos] = item; }
	public E getvalue(int pos) { return data[pos]; }
	public int length() { return listSize; }
	public void append(E item) { data[listSize++] = item; }

	
	public void insert(int pos, E item) {
		//끝에꺼부터 한칸씩 오른쪽으로 땡기기
		for (int i=listSize; i > pos; i--) 
			data[i] = data[i-1];
			
		//맨앞에 빈 배열에 item넣어주기
 		data[pos] = item;
 		listSize++;
	}
	
	public E remove(int pos) {
		//지울거 지움
		E ret = data[pos];
		
		//지운거 다음부터 한칸씩 왼쪽으로 땡기기
		for(int i=pos; i<listSize; i++) 
			data[i] = data[i+1];
		
		listSize--;
		return ret;
		}
	}	
}

 

(왼) insert, (오) remove

 

+ append와 insert의 차이점

• append는 걍 맨 끝에 넣는거
• insert는 원하는 특정 위치에 넣는거

 

 

---

 

 

LinkedList (연결 기반 리스트)

연결

데이터(item) + 포인터(Pointer)

 

 

연결 Class 구현

public class Link<E> {
	private E item;
	private Link<E> next; //선언 이해좀
	
	public Link(E item, Link<E> next) {
		this.item = item;
		this.next = nextval; //?
	}
	
	Link<E> next() { return next; }
	Link<E> setNext(Link<E> next) { return this.next = next; }
	E item() {return item; }
	E setIten(E item) { return this.item = item; }
}

 

 

리스트를 연결을 이용해 표현하자!

 

 

 

LinkedList Class 구현 (아직잘모르겠음 +더공부하장)

public class LinkedList<E> implements List<E> {
	
	private Link<E> head, tail;
	int size;
	
	public LinkedList() {
		head = tail = new Link<>(null, null);
		size = 0;
	}
	
	@Override
	public void clear() {
		head.setNext(null);
		size = 0;
	}
	
	@Override
	public void update(int pos, E item) {
		Link<E> curr = head; //curr은 무엇?
		for(int i=0; i<pos; i++) curr = curr.next();
		curr.setItem(item);
	}
	
	@Override
	public E getValue(int pos) {
		Link<E> curr = head;
		for(int i=0; i<pos; i++) curr = curr.next();
		return curr.item();
	}
	
	@Override
	public int length() {
		return size;
	}
	
	@Override
	public void append(E item) {
		tail = tail.setNext(new Link<>(item, null));
		size++;
	} 
	
	
	public void insert(int pos, E item) {
		Link<E> curr = head;
		for(int i=0; i<pos; i++) //여기서 pos는 무엇?
			curr = curr.next();
		
		curr.setNext(new Link<>(item, curr.next()));
		
		if(curr == tail)
			tail = curr.next();
		
		size++;
	}
	
	public E remove(int pos) {
		Link<E> curr = head;
		for(int i=0; i<pos; i++)
			curr = curr.next();
		
		E ret = curr.next().item();
		
		if(curr.next() == tail)
			tail = curr;
		
		curr.setNext(curr.next().next());
		
		size--;
		
		return ret;
	}
}