[리스트]선형리스트(연결리스트)

00. 알고가기: 자료구조의 분류

 

https://lee-mandu.tistory.com/462?category=633568

 

01. 선형리스트(연결리스트)

- 가장 단순한 구조, 데이터를 순서대로 나열해 놓은 자료구조
- 이야기 전달방식 : 한 사람을 건너뛰어 전달 할 수 없다.

▶︎ 노드(요소) : 머리, 꼬리/ 앞쪽, 다음
   - 데이터
   - 포인터 : 다음 노드를 가리킨다
   - [그림 9-2]에서 노드 C의 앞쪽 노드는 B, 다음 노트는 D이고 노드 C가 갖는 포인터는 다음 노드 D를 가리킨다.

▶︎ 배열로 선형 리스트 만들기

- 다음 노드 꺼내기 : 1만큼 큰 인덱스를 갖는 요소에 접근
- 노드의 삽입과 삭제 : 회원번호 55인 회원을 12,33 사이에 삽입하기 위해 삽입요소 다음의 모든 요소를 하나씩 뒤로 밀어야 한다.

배열로 구현한 선형리스트의 문제
1. 쌓이는 데이터의 크기를 미리 알아야 한다.
2. 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않다. 

 

 

02. 포인터로 연결리스트 만들기

- 연결리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애면 위의 문제를 해결할 수 있다.
- 자기참조형: 데이터용 필드인 data와 별도로 자기 자신과 같은 클래스형의 인스턴스를 참조하기 위한 참조용 필드 next를 가진다. 

 - 클래스형인 변수 data는 데이터 그 자체가 아니라 어디까지나 데이터에 대한 '참조'이다. 

public class LinkedList<E> {
	// 노드
	class Node<E> {
		private E data;			// 데이터
		private Node<E> next;	// 뒤쪽 포인터(다음 노드 참조)

		// 생성자
		Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
	}

	private Node<E> head;		// 머리 노드
	private Node<E> crnt;		// 선택 노드

	// 생성자
	public LinkedList() {
		head = crnt = null;
	}

▶︎ 검색과 삽입
- while 안 if문 : ptr의 값이 null이 되면 while문을 빠져나오는게 되고, 이를 판단하기 위해 데이터 obj와 스캔하고 있는 노드의 데이터 ptr.data를 comparator c로 비교한다. compare 메서드가 반환하는 값이 0이면 종료조건이 성립하여 검색 성공.

	// 노드 검색
	public E search(E obj, Comparator<? super E> c) {
		Node<E> ptr = head;							// 현재 스캔중인  노드

		while (ptr != null) {
			if (c.compare(obj, ptr.data) == 0) {	// 검색 성공
				crnt = ptr;
				return ptr.data;
			}
			ptr = ptr.next;							// 다음 노드를 선택
		}
		return null;								// 검색 실패
	}

	// 머리에 노드 삽입
	public void addFirst(E obj) {
		Node<E> ptr = head;							// 삽입 전의 머리 노드
		head = crnt = new Node<E>(obj, ptr);
	}

	// 꼬리에 노드 삽입
	public void addLast(E obj) {
		if (head == null)							// 리스트가 비어 있으면 
			addFirst(obj);							// 머리에 삽입
		else {
			Node<E> ptr = head;
			while (ptr.next != null)
				ptr = ptr.next;
			ptr.next = crnt = new Node<E>(obj, null);
		}
	}

▶︎ 삭제

	// 머리 노드 삭제
	public void removeFirst() {
		if (head != null)							// 리스트가 비어 있지 않으면
			head = crnt = head.next;
	}

	// 꼬리 노드  삭제
	public void removeLast() {
		if (head != null) {
			if (head.next == null)					// 노드가 하나만 있으면
				removeFirst();						// 머리 노드를 삭제
			else {
				Node<E> ptr = head;					// 스캔 중인  노드
				Node<E> pre = head;					// 스캔 중인  노드의 앞쪽 노드

				while (ptr.next != null) {
					pre = ptr;
					ptr = ptr.next;
				}
				pre.next = null;					// pre는 삭제 후의 꼬리 노드
				crnt = pre;
			}
		}
	}

	// 노드 p를 삭제
	public void remove(Node p) {
		if (head != null) {
			if (p == head)							// p가 머리 노드면
				removeFirst();						// 머리 노드를 삭제
			else {
				Node<E> ptr = head;

				while (ptr.next != p) {
					ptr = ptr.next;
					if (ptr == null) return;		// p가 리스트에 없습니다.  
				}
				ptr.next = p.next;
				crnt = ptr;
			}
		}
	}

	// 선택 노드를 삭제
	public void removeCurrentNode() {
		remove(crnt);
	}

	// 모든 노드를 삭제
	public void clear() {
		while (head != null)						// 노드에 아무것도 없을 때까지
			removeFirst();							// 머리 노드를 삭제
		crnt = null;
	}

▶︎ 출력

// 선택 노드를 하나 뒤쪽으로 이동
	public boolean next() {
		if (crnt == null || crnt.next == null)
			return false;							// 이동할 수 없음
		crnt = crnt.next;
		return true;
	}

	// 선택 노드를 출력
	public void printCurrentNode() {
		if (crnt == null)
			System.out.println("선택한 노드가 없습니다.");
		else
			System.out.println(crnt.data);
	}

	// 모든 노드를 출력
	public void dump() {
		Node<E> ptr = head;

		while (ptr != null) {
			System.out.println(ptr.data);
			ptr = ptr.next;
		}
	}

 

 

03. 연결리스트를 사용한 프로그램

▶︎  LinkedList.java

package chap09;
import java.util.Comparator;
// 연결 리스트 클래스

public class LinkedList<E> {
	// 노드
	class Node<E> {
		private E data;			// 데이터
		private Node<E> next;	// 뒤쪽 포인터(다음 노드 참조)

		// 생성자
		Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
	}

	private Node<E> head;		// 머리 노드
	private Node<E> crnt;		// 선택 노드

	// 생성자
	public LinkedList() {
		head = crnt = null;
	}

	// 노드 검색
	public E search(E obj, Comparator<? super E> c) {
		Node<E> ptr = head;							// 현재 스캔중인  노드

		while (ptr != null) {
			if (c.compare(obj, ptr.data) == 0) {	// 검색 성공
				crnt = ptr;
				return ptr.data;
			}
			ptr = ptr.next;							// 다음 노드를 선택
		}
		return null;								// 검색 실패
	}

	// 머리에 노드 삽입
	public void addFirst(E obj) {
		Node<E> ptr = head;							// 삽입 전의 머리 노드
		head = crnt = new Node<E>(obj, ptr);
	}

	// 꼬리에 노드 삽입
	public void addLast(E obj) {
		if (head == null)							// 리스트가 비어 있으면 
			addFirst(obj);							// 머리에 삽입
		else {
			Node<E> ptr = head;
			while (ptr.next != null)
				ptr = ptr.next;
			ptr.next = crnt = new Node<E>(obj, null);
		}
	}

	// 머리 노드 삭제
	public void removeFirst() {
		if (head != null)							// 리스트가 비어 있지 않으면
			head = crnt = head.next;
	}

	// 꼬리 노드  삭제
	public void removeLast() {
		if (head != null) {
			if (head.next == null)					// 노드가 하나만 있으면
				removeFirst();						// 머리 노드를 삭제
			else {
				Node<E> ptr = head;					// 스캔 중인  노드
				Node<E> pre = head;					// 스캔 중인  노드의 앞쪽 노드

				while (ptr.next != null) {
					pre = ptr;
					ptr = ptr.next;
				}
				pre.next = null;					// pre는 삭제 후의 꼬리 노드
				crnt = pre;
			}
		}
	}

	// 노드 p를 삭제
	public void remove(Node p) {
		if (head != null) {
			if (p == head)							// p가 머리 노드면
				removeFirst();						// 머리 노드를 삭제
			else {
				Node<E> ptr = head;

				while (ptr.next != p) {
					ptr = ptr.next;
					if (ptr == null) return;		// p가 리스트에 없습니다.  
				}
				ptr.next = p.next;
				crnt = ptr;
			}
		}
	}

	// 선택 노드를 삭제
	public void removeCurrentNode() {
		remove(crnt);
	}

	// 모든 노드를 삭제
	public void clear() {
		while (head != null)						// 노드에 아무것도 없을 때까지
			removeFirst();							// 머리 노드를 삭제
		crnt = null;
	}

	// 선택 노드를 하나 뒤쪽으로 이동
	public boolean next() {
		if (crnt == null || crnt.next == null)
			return false;							// 이동할 수 없음
		crnt = crnt.next;
		return true;
	}

	// 선택 노드를 출력
	public void printCurrentNode() {
		if (crnt == null)
			System.out.println("선택한 노드가 없습니다.");
		else
			System.out.println(crnt.data);
	}

	// 모든 노드를 출력
	public void dump() {
		Node<E> ptr = head;

		while (ptr != null) {
			System.out.println(ptr.data);
			ptr = ptr.next;
		}
	}
}

▶︎ LinckedListTest.java

package chap09;
import java.util.Scanner;
import java.util.Comparator;
// 연결 리스트 클래스 LinkedList<E>의 사용 예

public class LinkedListTester {
	static Scanner stdIn = new Scanner(System.in);

	// 데이터 (회원번호+이름)
	static class Data {
		static final int NO   = 1;		// 번호를 입력 받습니다.
		static final int NAME = 2;		// 이름을 입력 받습니다.

		private Integer no;				// 회원번호
		private String  name;			// 이름

		// 문자열을 반환합니다.
		public String toString() {
			return "(" + no + ") " + name;
		}

		// 데이터를 입력합니다.
		void scanData(String guide, int sw) {
			System.out.println(guide + "할 데이터를 입력하세요.");

			if ((sw & NO) == NO) {
				System.out.print("번호：");
				no = stdIn.nextInt();
			}
			if ((sw & NAME) == NAME) {
				System.out.print("이름：");
				name = stdIn.next();
			}
		}

		// 회원번호로 순서를 매기는 comparator
		public static final Comparator<Data> NO_ORDER =	 new NoOrderComparator();

		private static class NoOrderComparator implements Comparator<Data> {
			public int compare(Data d1, Data d2) {
				return (d1.no > d2.no) ? 1 : (d1.no < d2.no) ? -1 : 0;
			}
		}

		// 이름으로 순서를 매기는 comparator
		public static final Comparator<Data> NAME_ORDER = new NameOrderComparator();

		private static class NameOrderComparator implements Comparator<Data> {
			public int compare(Data d1, Data d2) {
				return d1.name.compareTo(d2.name);
			}
		}
	}

	// 메뉴 열거형
	enum Menu {
		ADD_FIRST(  "머리에 노드를 삽입"),
		ADD_LAST(   "꼬리에 노드를 삽입"),
		RMV_FIRST(  "머리 노드를 삭제"),
		RMV_LAST(   "꼬리 노드를 삭제"),
		RMV_CRNT(   "선택 노드를 삭제"),
		CLEAR(      "모든 노드를 삭제"),
		SEARCH_NO(  "번호로 검색"),
		SEARCH_NAME("이름으로 검색"),
		NEXT(       "선택 노드를 하나 뒤쪽으로 이동"),
		PRINT_CRNT( "선택 노드를 출력"),
		DUMP(       "모든 노드를 출력"),
		TERMINATE(  "종료");

		private final String message;				// 출력할 문자열 

		static Menu MenuAt(int idx) {				// 서수가 idx인 열거를 반환
			for (Menu m : Menu.values())
				if (m.ordinal() == idx)
					return m;
			return null;
		}

		Menu(String string) {						// 생성자
			message = string;
		}

		String getMessage() {						// 출력할 문자열을 반환
			return message;
		}
	}

	// 메뉴 선택
	static Menu SelectMenu() {
		int key;
		do {
			for (Menu m : Menu.values()) {
				System.out.printf("(%d) %s  ", m.ordinal(), m.getMessage());
				if ((m.ordinal() % 3) == 2 &&
					  m.ordinal() != Menu.TERMINATE.ordinal())
					System.out.println();
			}
			System.out.print("：");
			key = stdIn.nextInt();
		} while (key < Menu.ADD_FIRST.ordinal() || 
											key > Menu.TERMINATE.ordinal());
		return Menu.MenuAt(key);
	}

	public static void main(String[] args) {
		Menu menu;						// 메뉴
		Data data;						// 추가용 데이터 참조
		Data ptr;						// 검색용 데이터 참조
		Data temp = new Data();			// 입력용 데이터

		LinkedList<Data> list = new LinkedList<Data>();		// 리스트를 생성

		do {
			switch (menu = SelectMenu()) {
			 
			 case ADD_FIRST :								// 머리에 노드를 삽입
					data = new Data();
				 	data.scanData("머리에 삽입", Data.NO | Data.NAME);
					list.addFirst(data);
		 			break;

			 case ADD_LAST :								// 꼬리에 노드를 삽입
					data = new Data();
				 	data.scanData("꼬리에 삽입", Data.NO | Data.NAME);
			 		list.addLast(data);
			 		break;

			 case RMV_FIRST :								// 머리 노드를 삭제
					list.removeFirst();
					break;

			 case RMV_LAST :								// 꼬리 노드를 삭제
					list.removeLast();
					break;

			 case RMV_CRNT :								// 선택 노드를 삭제
					list.removeCurrentNode();
					break;

			 case SEARCH_NO :								// 회원번호로 검색
				 	temp.scanData("검색", Data.NO);
					ptr = list.search(temp, Data.NO_ORDER);
					if (ptr == null)
						System.out.println("그 번호의 데이터가 없습니다.");
					else
						System.out.println("검색 성공：" + ptr);
			 		break;

			 case SEARCH_NAME :								// 이름으로 검색
				 	temp.scanData("검색", Data.NAME);
					ptr = list.search(temp, Data.NAME_ORDER);
					if (ptr == null)
						System.out.println("그 이름의 데이터가 없습니다.");
					else
						System.out.println("검색 성공：" + ptr);
			 		break;

			 case NEXT :									// 선택 노드를 뒤쪽으로 이동
					list.next();
			 		break;

			 case PRINT_CRNT :								// 선택 노드의 데이터를 출력
					list.printCurrentNode();
			 		break;

			 case DUMP :									// 모든 노드를 리스트 순서로 출력
					list.dump();
			 		break;

			 case CLEAR :									// 모든 노드를 삭제
					list.clear();
			 		break;
			}
		} while (menu != Menu.TERMINATE);
	}
}

 

▶︎ Comparator<? super T> c