알고리즘2-1. 선형리스트(LinkedList 연결리스트)

LinkedList 연결리스트

- 자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키지만, 자료 순서에 따라 노드의 포인터 부분을 이용해 연결시킨 자료구조

노드의 삽입, 삭제 작업이 용이하다.	기억공간이 연속적으로 놓여있지 않아도 저장이 가능하다.
연결을 위한 포인터가 필요하기 때문에 기억공간이용 효율이 좋지 않다.	연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근속도가 느리다.
중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.	노드 구조를 사용하는 트리 등을 표현할 때 가장 적합한 자료구조이다.

리스트의 데이터는 노드(node) 또는 요소(element)라고 한다. 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.

처음에 있는 노드: 머리 노드(head node)	끝에 있는 노드: 꼬리 노드(tail node)
하나의 노드에 대해 바로 앞에 있는 노드: 앞쪽 노드(predecessor node)	바로 뒤에 있는 노드: 다음 노드(successor node)

Node<E>는 제네릭으로 구현되기 때문에 데이터 형 E는 임의의 클래스 형이 허용된다.(자유롭게 형지정 가능)
클래스형 변수인 data는 데이터 자체가 아니라 데이터에 대한 '참조'이다.
다음 노드를 참조하는 next 뒤쪽 포인터는 그 노드의 다음 노드의 대한 참조이지만 다음 노드가 없는 '꼬리 노드'의 포인터 값은 널을 참조한다!

1. 클래스 Node<E>형인 연결리스트를 클래스 LinkedListTest<E>로 구현한 프로그램

package al04_LinkedList;

public class LinkedListTest<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> current; // 선택 노드
    
	// LinkedListTest의 생성자
	public LinkedListTest() {  
		head = null;           // head node를 가리킴
		current = null;        // 현재 선택한 노드를 가리킴(다음 노드 참조)
	}

LinkedListTest<E>의 head, current

- head는 머리 노드를 가리킴

- current 현재 선택한 노드를 가리킴(검색 || 삭제의 용도로 사용)

LinkedListTest<E>의 생성자

- head, current를 null로 초기화해서 노드가 하나도 없는 비어있는 연결리스트를 생성

- head = current = null; 이렇게 한 줄로 사용할 수 있다.

*연결 리스트안의 노드의 수를 판단하는 방법*

head == null : 연결 리스트가 비어 있는지 확인한다.
head.next == null : 노드가 1개인지 확인한다. (head는 data와 next로 나뉘어있는데 next는 다음 노드의 참조를 한다. next가 null 값이라면 다음 노드가 없다는 뜻이다.)
head.next.next == null : 노드가 2개인지 확인한다. ( 첫번째 노드의 데이터는 head.data이고, 두번째 노드의 데이터는 head.next.data이다.

* 꼬리 노드인지 판단하는 방법*

- point.next == null : point변수가 가리키는 노드가 꼬리 노드인지 확인한다.

2. 머리노드에 데이터를 삽입을 하는 addFirst메서드

2-1. LinkedListTestMain 에서 매개변수 E data를 생성

public class LinkedListTest<E> {

// 머리에 노드 삽입
public void addFirst(E data) {  // 번호와 이름이 들어있는 data(LinkedListTestMain에서 생성) 
	//지금 현재 헤더
	Node<E> point = head;
	head = current = new Node<E>(data, point);
    
	}
}

현재 리스트에 데이터가 없어서 삽입전의 머리노드를 head 노드의 포인터를 point에 저장.

현재 생성된 노드는 head노드이면서 == current node가 된다.

노드의 데이터는 data가 되고, 뒤 쪽 포인터를 가리키는 next는 point가 된다. 현재 선택된 노드는 머리 노드에 추가된 노드로 업데이트한다.

package al04_LinkedList;

import java.util.Scanner;

public class LinkedListTestMain {
	static Scanner scan = new Scanner(System.in);
	
	// 번호와 이름을 저장할 수 있는 내부클래스	
	static class Data{  // 데이터(번호와 이름)
		private Integer no;   // 객체로 사용하기 위해서 참조형으로(오토박싱) 
		private String name;  
		
		// 멤버변수
		static final int NO = 1;   // 번호를 입력받을지 확인
		static final int NAME = 2; // 이름을 입력받을지 확인
		
		// 문자열을 반환
		public String toString() {
			return no + ":" + name;
		}
 }

- 외부에서 사용하지 못하게 이름과 번호의 접근제어자를 private으로 설정했고, 객체로 사용할 수 있도록 참조형으로 했다.(오토박싱)

- 번호를 입력받을 때는 1로 입력받을 때는 2로

- 출력은 번호: 이름 이렇게 된다.

3. 꼬리노드에 데이터를 삽입을 하는 addLast메서드

-> 리스트가 비어 있는지 아닌지 먼저 확인(head==null )하고 경우에 따라 작업 수행

리스트가 비어 있는 경우: addFirst( )와 동일

리스트가 비어 있지 않은 경우: 리스트의 꼬리에 노드를 삽입

public class LinkedListTest<E> {

	// 꼬리에 노드 삽입 
	public void addLast(E data) {
		if(head == null) {    // 연결리스트가 비어 있는지 확인(저장된 리스트가 없다면?)
			addFirst(data);   // addFirst로 head노드에 삽입
            
		}else { // 저장된 리스트가 있다.(비어있지 않다.)
			Node<E> point = head;        
			while(point.next != null) { 
				point = point.next;
		}
		// point는 next가 null인 노드이다.
		current = point.next = new Node<E>(data, null);
	}
}

리스트가 비어있지 않을 때는 먼저 꼬리 노드를 찾아야 한다.

머리 노드를 가리키도록 한 point가 노드를 계속해서 다음 노드를 가리키도록 업데이트 하는 과정을 반복한다. 이렇게 반복하게 되면 노드를 처음부터 스캔하게 된다.

point.next가 가리키는 노드가 null이 되면(다음 노드가 없다면) while문은 종료된다.

current = point.next = new Node<E>(data, null)

여기서 노드의 데이터는 data가 되고, 뒤 쪽 포인터를 가리키는 next는 null이 된다. 현재 선택된 노드는 꼬리노드에 추가된 노드로 업데이트 한다.

4. 머리노드를 삭제하는 removeFirst 메서드

public class LinkedListTest<E> {

	// 머리노드 삭제
	public void removeFirst() {
		if(head != null) { // 노드가 존재하면(리스트가 비어있지 않는 경우)
			current = head  = head.next;
		}
	}
}

리스트가 비어 있지 않은 경우(head != null)에만 삭제를 실행한다.

머리 노드에 대한 참조 head에 두 번째 노드에 대한 참조 head.next를 대입해서 head가 가리키는 노드를 두 번째 노드로 선택한다. 현재 선택된 노드(current)는 삭제된 노드가 가리키는 노드(두 번째 노드)

5. 꼬리노드를 삭제하는 removeLast 메서드

- 리스트에 노드가 몇 개 있는지에 따라 그 경우에 해당하는 작업을 한다.

- 리스트에 노드가 1개만 있는 경우엔 removeFirst( )와 동일, 리스트에 노드가 2개 이상 있는 경우는 예제로!

public class LinkedListTest<E> {

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

먼저 '꼬리 노드'와 '꼬리 노드로부터 두 번째 노드'를 찾는다.

while문 종료시, point는 꼬리 노드를 가리키고, pre는 꼬리로부터 두 번째 노드를 가리킨다.

while문은 addLast의 메서드와 거의 같은데 현재 스캔 중인 노드(point)의 앞쪽 노드(pre)를 참조하는 변수가 추가 되었다.

pre.next = null; current = pre;

현재 스캔 중인 꼬리 노드(point)의 앞쪽 노드(pre) 포인터에 null을 대입한다. (그러면 pre는 꼬리 노드가 된다)

현재 선택된 노드는 pre(새로운 꼬리 노드)

6. 임의의 노드를 삭제하는 remove 메서드와 현재 선택한 노드를 삭제하는 removeCurrent메서드, 모든 노드를 삭제하는 clear 메서드

(1) remove

- 선택한 노드가 머리 노드인지 아닌지에 따라 그 경우에 해당하는 작업을 한다.

- 삭제하려는 delNode가 머리 노드인 경우엔 removeFirst( )로 처리, delNode가 머리노드가 아닌 경우엔 예제로!

(2) removeCurrent

- 현재 선택된 노트를 삭제하는 노드로 remove 메서드에 current를 건네주고 처리를 맡긴다.

- 이 메서드를 실행하면 선택 노드 current가 참조하는 곳은 삭제한 노드의 앞쪽 노드로 업데이트 된다.

(3) clear

- 모든 노드를 삭제하는 메서드

- 연결 리스트가 비어있는 상태(head == null)까지 머리 요소의 삭제를 반복해 모든 노드를 삭제한다.

- 리스트가 비어있게 되면서 선택 노드 current의 값도 null로 업데이트 된다.

public class LinkedListTest<E> {

	// 노드삭제
	public void remove(Node<E> delNode) {
		if(head != null) { 	      // 노드가 있을 경우
			if(head == delNode) { // 삭제할 노드(delNode)가 head node면
				removeFirst();    // head node 삭제(delNode == heade node여서)
			} else {
				Node<E> point = head;
                
				while(point.next != delNode) { // delNode의 앞노드 찾기
					point = point.next;
				}
				// point는 delNode의 이전노드이다.  
				point.next = delNode.next;
				current = point;
			}
		}
	}
    
      // 선택노드 삭제
	public void removedCurrent() {
		remove(current);
	}
    
    	// 모든노드 삭제
	public void clear() {
		while(head != null) 
			removeFirst();
		current = null;
	}
    
}

else 구문은 노드 delNode의 앞쪽 노드를 찾는 과정이다.

while문은 스캔을 머리 노드(point)에서 시작해 선택 노드의 delNode의 뒤쪽포인터 delNode.next가 point와 같을 때까지 실행한다.

point.next = delNode.next;

delNode의 뒤쪽 포인터 delNode.next를 point.next에 대입하게 되면 delNode는 어디에서도 참조하지 않기 때문에 자동으로 해제 되고 앞의 point가 현재 선택노드가 되게 된다.

7. 모든 노드를 출력(표시)하는 dump 메서드

- 리스트의 순서대로 모든 노드를 표시하는 메서드로 머리 노드부터 꼬리 노드까지 스캔하면서 각 노드의 데이터 point.data를 표시(출력)한다.

- 이메서드는 current값을 업데이트 하지 않아도 된다.

public class LinkedListTest<E> {
	// 출력
	public void dump() {
		Node<E> point = head;
        
		while(point != null) {           // 리스트에 노드가 존재하다면, 
		System.out.println(point.data);  // 노드의 data를 출력!
		point = point.next;              // while문이 실행되는 동안 계속 그 다음 노드를 스캔
		}
	}
}

1. 클래스 LinkedListTest<E>에서 만든 메서드를 LinkedListTestMain에서 호출하고 사용하기

package al04_LinkedList;

import java.util.Scanner;

public class LinkedListTestMain {
	static Scanner scan = new Scanner(System.in);
	
	// 번호와 이름을 저장할 수 있는 내부클래스	
	static class Data{  // 데이터(번호와 이름)
		private Integer no;   // 객체로 사용하기 위해서 참조형으로(오토박싱) 
		private String name;  
		
		// 멤버변수
		static final int NO = 1;   // 번호를 입력받을지 확인
		static final int NAME = 2; // 이름을 입력받을지 확인
		
		// 문자열을 반환
		public String toString() {
			return no + ":" + name;
		}
		
		// 번호 또는 이름을 입력받는 메서드
		public void scanData(String msg, int s) {
			// s에는 1, 2, 3중에 하나가 대입된다.
			if((s & NO) == NO)             {// 비트 && 연산
				System.out.print("번호-> "); // 번호입력
				no = scan.nextInt();
			}
			if((s & NAME) == NAME) {
				System.out.print("이름-> ");  // 이름입력
				name = scan.next(); // 공백 기준으로 단어 한개 입력 
			}
		}
	}
	
	// 메뉴를 열거형으로 만들기
	enum Menu {
		ADD_FIRST("머리에 노드 삽입"),
		ADD_LAST("꼬리에 노드 삽입"),
		REMOVE_FIRST("머리 노드 삭제"),
		REMOVE_LAST("꼬리 노드 삭제"),
		REMOVE_CURRENT("선택 노드 삭제"),
		CLEAR("모든 노드 삭제"),
		DUMP("모든 노드 출력"),
		TERMINATE("종료");
		
		private final String message;
		
		static Menu MenuAt(int idx) {
			for(Menu m:Menu.values()) {
				if(m.ordinal() ==idx)
					return m;
			}
			return null;
		}
		
		Menu(String str) {
			message = str;
		}
		
		String getMessage() {
			return message;
		}
	}
	
	// 메뉴를 표시하고 메뉴의 index를 입력받아 선택한 메뉴객체 리턴하는 메서드
	static Menu SelectMenu() {
		int key;
		do {
			for(Menu m:Menu.values()) {
				System.out.printf("(%d) %s ", m.ordinal()+1, m.getMessage());
			}
			System.out.print("-> ");
			key = scan.nextInt()-1;  // 사용자가 입력한 값
		}while(key<Menu.ADD_FIRST.ordinal() || key>Menu.TERMINATE.ordinal());
		
		return Menu.MenuAt(key);
	}

	public static void main(String[] args) {
		Menu menu; // 선택한 메뉴
		LinkedListTest<Data> list = new LinkedListTest<Data>();
		
		do {
			//메뉴 표시 
			Data data;
			menu = SelectMenu();
			switch(menu) {
			case ADD_FIRST: // 머리에 노드삽입
				data = new Data();
				data.scanData("머리노드삽입", Data.NO | Data.NAME );  // 비트 || 연산
				list.addFirst(data);// List에 저장 
				break;
		
			case ADD_LAST:  // 꼬리에 노드삽입
				data = new Data();
				data.scanData("꼬리노드삽입", Data.NO | Data.NAME);
				list.addLast(data);
				break;
				
			case REMOVE_FIRST:  // 머리노드 삭제
				list.removeFirst();
				break;
				
			case REMOVE_LAST:   // 꼬리노드 삭제
				list.removeLast();
				break;
				
			case REMOVE_CURRENT:  // 선택노드 삭제
				list.removedCurrent();
				break;
				
			case CLEAR:          // 모든노드 삭제
				list.clear();
				break; 
				
			case DUMP:           // 모든노드 출력
				list.dump();
				break;
			}
		}while(menu!= Menu.TERMINATE);
		System.out.println("프로그램이 종료되었습니다.");
	}
}

2022.01.08 - [멀티캠퍼스 풀스택 과정/Java의 정석] - 자바의 정석8-2 ArrayList, LinkedList

자바의 정석8-2 ArrayList, LinkedList

ArrayList - ArrayList는 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일! - Vector는 ArrayList와 달리 자체적으로 동기화 처리가 되어 있음(Vector와 ArrayList의 차이는 동기화 유무) - List인터..

everysmallstep.tistory.com

2022.01.07 - [멀티캠퍼스 풀스택 과정/Java의 정석] - 자바의 정석6-4 오토박싱 & 언박싱

자바의 정석6-4 오토박싱 & 언박싱

오토박싱 & 언박싱 int(기본형) -> Integer(래퍼클래스:참조형): 오토박싱(Auto boxing) Integer(래퍼클래스:참조형) -> int(기본형): 언박싱(un boxing) 컴파일러가 자동으로 래퍼클래스의 객체인 Integer를 in..

everysmallstep.tistory.com

저작자표시

'멀티캠퍼스 풀스택 과정 > 알고리즘' 카테고리의 다른 글

알고리즘2-2. 이진탐색알고리즘 (0)	2022.01.29
소수판별 알고리즘 (0)	2022.01.28
알고리즘1-6. 정렬(Sorting): 버블정렬, 선택정렬, 삽입정렬, 퀵정렬 (0)	2022.01.26
알고리즘1-5. 재귀알고리즘 (0)	2022.01.26
알고리즘1-4. 큐(Queue) (0)	2022.01.26