[JAVA] MyLinkedList 구현(LinkedList 기능 따라잡기)

1. MyLinkedList를 구현 조건

• 양방향으로 구현
• CRUD(add, get, set, delete) 기본적으로 구현(삭제, 삽입 위치는 상관 없음)
• <> 제네릭은 구현해도 되고 안해도 됨

2. 구현 코드

• class Node<T>
  • 양방향이기 때문에 클래스 Node의 필드를 Node left, Node right를 선언하고 T num에 값을 넣도록 함
  • <T>는 제네릭으로 원하는 타입을 사용 할 수 있도록 함

class Node<T> {
	Node left;
	Node right;
	T num;
	
	Node(T n) {
	   num = n;
	}
}

• MyLinkedList<T>
  
  • MyLinkedList 객체를 생성했을 때 객체가 CRUD가 일어 날 수 있도록 add(), get(), set(), delete() 메소드를 직접 구현 해 주었다.
  • C언어의 연결리스트 개념과 동일하게 접근하면 이해하기가 쉽다.
  • 환형리스트로 구현을 해 주었다.
• public String toString() -> StringBuilder 사용 Why?
  • 보통 string+string을 사용하는 연산을 하게 되면 새로운 string 객체를 생성하게 된다. 객체를 생성함으로써 메모리 할당과 메모리 해제를 발생시키며 더하는 연산이 많아진다면 성능적으로 좋지 않다.
  • 그래서 StringBuilder를 사용한다.
  • 이것은 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라 기존의 string 객체에 데이터를 더하는 방식을 이용한 것이기 때문에 속도도 빠르며 상대적으로 부하가 적다.

public class MyLinkedList<T> {
	Node<T> head;
	
	MyLinkedList() {
	   head = null;
	}
	
	// 리스트 추가
	void add(T n) {
	   if (head == null) {
	      head = new Node<T>(n);
	      head.right = head;
	      head.left = head;
	
	   } else {
	      Node<T> node = new Node<T>(n);
	      Node<T> tail = head.left;
	      head.left = node;
	      tail.right = node;
	      node.left = tail;
	      node.right = head;
	   }
	}
	
	// 리스트 삭제
	void delete() {
	   if (head == null)
	      System.out.println("없음");
	   else if (head.right == head && head.left == head)
	      head = null;
	   else {
	      Node nodeDelete = head.left;
	      Node nodePrev = nodeDelete.left;
	      Node nodeNext = nodeDelete.right;
	
	      nodePrev.right = nodeNext;
	      nodeNext.left = nodePrev;
	   }
	}
	
	// 리스트 읽기
	T get(int index) {
	   Node<T> nodeGet = head;
	   for (int i = 0; i < index; i++) {
	      nodeGet = nodeGet.right;
	   }
	   return nodeGet.num;
	}
	
	// 리스트 갱신
	void set(int index, T num) {
	   Node<T> nodeGet = head;
	   for (int i = 0; i < index; i++) {
	      nodeGet = nodeGet.right;
	   }
	   nodeGet.num = num;
	}

	@Override
	public String toString() {
	   StringBuilder sb = new StringBuilder();
	   sb.append("[");
	   Node nowNode = head;
	   do {
		  sb.append(" ");
	      sb.append(nowNode.num);
	      sb.append(" ");
	      nowNode = nowNode.right;
	   } while (nowNode != head);
	   sb.append("]");
	   return sb.toString();
	}
}

• main()

public class Main {
	public static void main(String[] args) {
		MyLinkedList<Integer> list = new MyLinkedList<Integer>();
		
		// 랜덤 값을 이용하여 10개의 값 추가
		for(int i = 0 ; i < 10 ; i++) {
			list.add((int)((Math.random() *100) % 100));
		}
		
		System.out.println("list   print : "+list);
		
		// list 삭제 : 가장 마지막 노드 삭제되도록 구현함
		list.delete();
		System.out.println("delete after : "+list);
		
		// get()
		System.out.println("get(4) print : "+list.get(4));
		
		// set() : update
		list.set(1, 20);
		System.out.println("set(1) print : "+list);
	}
}

• 실행결과

 

 

2019.07.24(수) [MyLinkedList project]