[JAVA] 단순연결리스트의 구현 - 학생부 입력 예제

연결리스트는 노드들의 연속.

 

노드는 해당 노드의 데이터 (항목)을 저장하는 item과,

다음 순서의 노드를 가리키는 next로 이루어져있다.  (단순연결리스트 기준)

 

→ 노드는 item과 next를 필드로 가지는 클래스로 구현하고,

각 노드는 해당 클래스로부터 생성한 객체이다.

 

** 학생부 입력 예제 - 단순연결리스트로 구현 **

 

단순연결리스트의 노드 클래스:

//단순연결리스트의 노드 클래스

public class Node {
	private String item;  //데이터 (항목)을 저장
	private Node next; //다음 노드의 레퍼런스 저장
	//생성자 - 해당 노드의 항목 저장, 다음 노드의 레퍼런스 저장
	Node(String item, Node next) {
		this.item = item;
		this.next = next;
	}
	//getter, setter
	public String getItem() {
		return item;
	}
	public Node getNext() {
		return next;
	}
	public void setItem(String item) {
		this.item = item;
	}
	public void setNext(Node next) {
		this.next = next;
	}
	
	// 학생부에 입력된 학생의 학번을 반환하는 메소드
	int getID() {
		int space = item.indexOf(" ");
		int ID = Integer.parseInt(item.substring(space+1));
		return ID;
	}
	
}

학생부 연결리스트 클래스:

//단순연결리스트의 클래스
// 학생부 입력을 위한 연결리스트이므로, 학생부 데이터(이름+학번)을 하나의 String으로 보았다.
import java.util.NoSuchElementException;
public class SingleList {
	Node head; //가장 앞 순서의 노드
	int size;      //링크드리스트에 저장된 노드 수
	//생성자
	SingleList() {
		head = null;
		size = 0; 
	}

	//탐색 메소드 - 탐색하고자 하는 노드가 링크드리스트에 저장되어있는지 
	int search(String target) {
		Node a = head; //맨 앞 노드서부터 탐색
		for (int i = 0; i < size; i++) {
			if (a.getItem().equals(target)) {
				return i;
			}
			a = a.getNext(); //다음 노드로 이동
		}
		return -1; 
	}
	//빈 리스트에 노드 저장시.
	void setFirst(Node newNode) {
		head = newNode;
		size++;
	}
	//삽입 
	void insert(Node newNode, int ID) {
		Node a = head;
		if (a.getID() > ID) {  // 맨 앞에 삽입하는 경우
			newNode.setNext(a);
			head = newNode;
		}
		else {
			for (int i = 0; i < size; i++) {
				if (a.getNext() == null) {break;}
				if (a.getNext().getID() > ID) {break;}
				a = a.getNext();
			}
			if (a.getNext() == null) {  // 가장 끝에 삽입하는 경우
				a.setNext(newNode);
			}
			else { // 중간에 삽입하는 경우
				newNode.setNext(a.getNext());
				a.setNext(newNode);
			}
		}
		size++;
	}
	//삭제 - 첫 노드
	void deleteFront() {
		if (size == 0) { 
			throw new NoSuchElementException(); // 저장된 데이터(노드) 없을 시 강제 종료.
		} 
		head = head.getNext();
		size--;
	}
	//삭제 - 중간 노드 or 끝 노드
	void deleteMid(String target) {
		if (target == null) { 
			throw new NoSuchElementException(); // 저장된 데이터(노드) 없을 시 강제 종료.
		} 
		Node a = head;
		for (int i = 0; i < size-1; i++) {
			if (a.getNext().getItem().equals(target)) {
				break;
			}
			a = a.getNext();
		}  // a 레퍼런스 변수에 target을 항목으로 갖고 있는 노드의 '직전'노 저장.
		if (a.getNext().getNext() == null) { // 삭제하려는 노드가 가장 끝 노드인 경우
			a.setNext(null);
		}
		else {
			a.setNext(a.getNext().getNext());
		}
		size--;
	}
	
	//연결리스트의 모든 노드를 순차적으로 출력하는 메소드
	void print() {
		Node a = head;
		for (int i = 0; i < size; i++) {
			System.out.println(a.getItem());
			a = a.getNext();
		}
	}
}

main 클래스: 

//   전제: 입력받는 학생 이름의 가나다 순서는 학번의 순서와 동일하게 입력한다

//       ex)  강호동 123 이승기 124 허준 129 => (O)

//              강호동 123 이승기 129 허준 124 => (X)

//       만약 학번의 순서와 가나다 순서가 다르게 입력되는 경우 (위 예의 둘째 줄), 학번의 순서를 우선으로 정렬한다.

SingleList students = new SingleList();
		
		System.out.println("**************** 학생부 ******************");
		System.out.println("이름과 학번(3자리)을 << 공백으로 구분하여 >> 입력:");
		
		while (true) {
			String st = scanner.nextLine();
			if (st.equals("print")) {
				students.print();
				System.out.println();
			}
			else if (students.size == 0) { // 빈 리스트에 저장시.
				students.setFirst(new Node(st, null));
			}
			else { 
				//이미 존재하는 학생을 또 입력했다면 해당 학생 노드 삭제.
				if (students.search(st) == 0) { // 맨 앞 학생 삭제시
					students.deleteFront();
				}
				else if (students.search(st) != -1) { // 중간 or 끝 학생 삭제시
					students.deleteMid(st);
				}
				// 이미 존재하는 학생이 아니라 새로운 학생 입력시 삽입.
				else {
					Node newNode = new Node(st, null);
					students.insert(newNode, newNode.getID());
				}
			}
		}

 

실행 결과: