Java - 싱글 연결리스트를 통해 다항식 계산

1. 문제 (다항식 계산)

---

2. 생각

• "MySingleLinkedList" 클래스는 해더 노드와 연결 리스트의 사이즈 정보를 담고 있으며, 연결 리스트에 노드 추가 및 삭제 등을 다루는 메서드를 갖고 있다. 
• "Node" 클래스는 연결리스트의 노드로서 데이터와 다음 노드의 참조를 갖고 있다.
• add 명령어를 수행하기 위해서 다음과 같은 과정 수행
  ▶  입력 받은 항의 지수와 traverse를 이용하여 입력 받은 항보다 지수가 작거나 같은 위치를 찾는다.
  ▶  만약 현재 노드가 null이 아닌 동시에 입력받은 지수와 동일하다면 
        추가하려는 항과 동일한 항이 이미 존재하기 때문에 단순히 계수만 수정
  ▶ 만약 현재 노드가 null이라면 동일한 항은 존재하지 않고, 추가하려는 항의 지수는 다항식내에서 가장 작다는 것을
       의미
  ▶  만약 현재 노드가 null은 아니지만, 입력 받은 지수가 동일하지 않다면, 동일한 항은 존재하지 않지만, 적절한 위치
       (= 다항식내에서 지수를 내림차순 정리했었을 때, 적절한 위치)를 찾은 상태
  ▶ 위 2 가지 경우에는 새로운 항을 생성하고, 해당 위치에 삽입한다.
  ▶ 만약 계수가 0이라면 remove 메서드를 이용하여 해당 항을 다항식에서 삭제

 

---

3. 풀이 및 코드 분석

3.1. Polynomial

public class Polynomial {
	private String name;
	private MySingleLinkedList<Term> terms;
	
	public Polynomial(String name) {
		this.name = name;
		terms = new MySingleLinkedList();
	}
	
	// *** Main functions ***
	// 1. add a term
	public void addTerm(int newCoef, int newExpo) {
		if(newCoef==0) {
			System.out.println("Coefficient is Zero.");
			return;
		}
		
		Node<Term> before = null;
		Node<Term> current = terms.getHead();
		
		while(current!=null && current.getData().getExpo()>newExpo) {
			before = current;
			current = current.getNext();
		}

		if(current!=null&&current.getData().getExpo()==newExpo) {
			handleModifyNode(before, current, newCoef);
		}else {
			handleNewNode(before, newCoef, newExpo);
		}
	}
	
	// 2. calculate a polynomial
	public void calcPoly(int value) {
		Node<Term> current = terms.getHead();
		double sum = 0;
		
		while(current!=null) {
			sum += current.getData().calcTerm(value);
			current = current.getNext();
		}
		
		System.out.printf("   Result of calculation: %f\n", sum);
	}
	
	// 3. print a polynomial
	public void printPoly() {
		StringBuilder sb = new StringBuilder();
		sb.append(String.format("   %s(x) =", name));
		
		Node<Term> node = terms.getHead();
		
		while(node!=null) {
			if(node.equals(terms.getHead()))
				sb.append(" " + node.getData().toString() + " ");
			else {
				if(node.getData().getCoef()<0)
					sb.append("- " + node.getData().toString() + " ");
				else 
					sb.append("+ " + node.getData().toString() + " ");
			}
			
			node = node.getNext();
		}
		
		System.out.println(sb.toString());
	}
	
	// *** Extra functions ***
	// 1. Add a new node
	private void handleNewNode(Node<Term> before, int newCoef, int newExpo) {
		Term newTerm = new Term(newCoef, newExpo);
		
		if(before==null)
			terms.addFirst(newTerm);
		else 
			terms.addAfter(before, newTerm);		
	}
	
	// 2. Modify a term
	private void handleModifyNode(Node<Term> before, Node<Term> current, int newCoef) {
		int coef = current.getData().getCoef();		
		current.getData().setCoef(coef += newCoef);
		
		if(current.getData().getCoef()==0) {
			if(current.equals(terms.getHead()))
				terms.removeFirst();
			else
				terms.removeAfter(before);
		}
		
	}
	
	// 3. Get a name
	public String getName() {
		return name;
	}
}

 3.2. Node & Term

public class Node<T> {
	private T data;
	private Node<T> next;
	
	// Constructor
	public Node(T data) {
		this.data = data;
		this.next = null;
	}

	// Getter & Setter
	public T getData() {
		return data;
	}

	public Node<T> getNext() {
		return next;
	}

	public void setData(T data) {
		this.data = data;
	}

	public void setNext(Node<T> next) {
		this.next = next;
	}
}

public class Term {
	private int coef;
	private int expo;
	
	// Constructor
	public Term(int coef, int expo) {
		this.coef = coef;
		this.expo = expo;
	}
	
	// Getter & Setter
	public int getCoef() {
		return coef;
	}

	public int getExpo() {
		return expo;
	}

	public void setCoef(int coef) {
		this.coef = coef;
	}

	public void setExpo(int expo) {
		this.expo = expo;
	}

	// Calculate a term
	public double calcTerm(int value) {
		return coef*Math.pow(value, expo);
	}
	
	// Print a term
	public String toString() {
		if(expo==0) {
			if(coef<0)
				return String.format("%s", -coef);
			else
				return String.format("%s", coef);
		}else if(expo==1) {
			if(coef==1 || coef==-1)
				return "x";
			else if(coef<0)
				return String.format("%dx", -coef);
			else 
				return String.format("%dx", coef);
		}else {
			if(coef<0)
				return String.format("%dx^%d", -coef, expo);
			else
				return String.format("%dx^%d", coef, expo);
		}
	}
}

---

4. 메모

• 싱글 연결리스트(Single linked list)에서 노드를 수정, 삭제, 추가 등을 하기 위해서는 대상이 되는 노드가 필요한 것이 아니라 직전 노드가 필요하다.