연결리스트와 Iterator 1

객체지향 프로그래밍

 

Information Hiding

Data Encapsulation

Abstract Data Type 

 

본질적으로 비슷한 내용이다.

 

인터페이스와 구현의 분리가 가장 중요한 원칙이다.

 

연결리스트는 리스트 라는 추상적인 데이터 타입을 구현하는 

한가지 방법일 뿐이다. 

 

사용자는 리스트에 데이터를 삽입, 삭제, 검색할 수 있으면 된다.

그것의 구현에 대해서 세부적으로 알 필요는 없다.

 

인터페이스와 구현을 분리하면 코드의 모듈성이 증가하며,

코드의 유지/보수, 코드의 재사용이 용이해진다.

 

사용자는 Interface만 알면 되고

Implementation에 대해서는 알 필요도 없고

알 수도 없게 해야한다.

 

package section7;

import section6.Node;

public class MySingleLinkedList<T> {
	
	public Node<T> head;
	public int size = 0;
	
	public MySingleLinkedList() {
		head = null;
		size = 0;
	}
	

private static class Node<T> {
	
	public T data;
	public Node<T> next;
	
	public Node(T data){
		this.data = data;
		next = null;
	}
	
}
	
	private void addFirst(T item) {
		Node<T> newNode = new Node<T>(item);
		newNode.next = head;
		head = newNode;
		size++;
	}
	
	private void addAfter(Node<T> before, T item) {
		Node<T> temp = new Node<T>(item);
		temp.next = before.next;
		before.next = temp;
		size++;
	}
	
	
	private T removeFirst() { //delete
		if(head==null) {
			return null;
		}
		else {
			T temp = head.data;
			head = head.next;
			size--;
			return temp;
		}
	}
	
	private T removeAfter(Node<T> before) {
		if(before.next==null) {
			return null;
		}
		else {
			T temp = before.next.data;
			before.next = before.next.next;
			return temp;
		}
		
	}
	
	public int indexOf(T item) { //search
		Node<T> p = head;
		int index = 0;
		while(p != null) {
			if(p.data.equals(item)) {
				return index;
			}
			else {
				p = p.next;
				index++;
			}
		}
		return -1;
	}
	
	private Node<T> getNode(int index){
		if(index<0 || index>=size) {
			return null;
		}
		else {
			Node<T> p = head;
			for(int i=0; i<index; i++) {
				p =p.next;
			}
			return p;
		}
		
	}
	
	public T get(int index) {
		if(index<0 || index>=size) {
			return null;
		}
			return getNode(index).data;		
	}
	
	public void add(int index, T item) {
		if(index <0||index >size) {
			return;
		}
		if(index==0) {
			addFirst(item);
		}
		else {
		Node<T> q = getNode(index-1);
		addAfter(q, item);
		}
	}
	
	public T remove(int index) {
		if(index < 0 || index >= size) {
			return null;
		}
		if(index ==0) {
			return removeFirst();
		}
		Node<T> prev = getNode(index-1);
		return removeAfter(prev);
	}
	
	public T remove(T item) {
		Node<T> p = head;
		Node<T> q = null;
		while(p != null && !p.data.equals(item)) {
			q = p;
			p=p.next;
		}
		if(p==null)
			return null;
		if(q==null)
			return removeFirst();
		else
			return removeAfter(q);	
	}
	
	public int size() {
		return size;
	}
	
	public static void main(String[] args) {
		
	}

}

기존에 만들었던 연결리스트 클래스이다.

 

인터페이스와 구현의 분리를 위해 

이너 클래스로 Node 클래스를 내부에 생성하고

Node 클래스를 이용하는 메서드들을 private로

변경해주는 작업을 하였다.

 

인터페이스를 생성하여

 

T get(int index)

void add(int index, T item)

T remove(int index)

boolean remove(T item)

int indexOf(T item)

int size()

 

메서드를 정의할 것이다.