[Java] 연결 리스트(LinkedList)

💡 LinkedList 특징

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
• 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함(정해진 크기가 없음)
• 연결 리스트의 i 번째 요소를 찾는데 걸리는 시간은 요소의 개수에 비례 : O(n)
• jdk 클래스 : LinkedList

🧑🏻‍💻 LinkedList 구현하기

MyListNode.java

public class MyListNode {
	
	//리스트 객체
	
	private String data; // 데이터
	public MyListNode next; // 다음 노드를 가리키는 링크
	
	public MyListNode() {
		//디폴트 생성자
		
		//맴버 변수 null 로 초기화
		data = null;
		next = null;
	}
	
	public MyListNode(String data) {
		
		//data를 매개변수로 갖는 생성자
		this.data = data;
		
		this.next = null;
	}
	
	public MyListNode(String data, MyListNode link) {
		// date 와 다음 요소를 가리키는 MyListNode 형의 link 로 초기화
		this.data = data;
		this.next = link;
	}
	
	public String getData() {
		return data; //데이터 반환
	}
	
	
	
	

}

---

MyLinkedList.java

public class MyLinkedList {
	
	private MyListNode head; //첫번째 노드
	int count; //데이터 수
	
	public MyLinkedList() {
		
		//생성자 
		//맴버 변수 초기화
		head = null;
		count = 0;
	}
	
	public MyListNode addElement( String data ) {
		
		MyListNode newNode;
		
		
		if(head == null) {
			
			newNode = new MyListNode(data); //다음 노드가 없기 때문에, data 매개변수로 생성
			head = newNode; //첫번째 노드로 현재 노드 설정
		}
		else {
			
			newNode = new MyListNode(data); //마지막 노드이기 때문에 다음노드가 없으므로, data 매개변수로 생성
			MyListNode temp = head; //현재 맨 첫 노드를 ..임시로 담을 변수에 설정
			while(temp.next != null) {
				//처음부터 끝까지 : 마지막 노드를 찾아서 [ 자신의 다음 노드가 없는 노드 ]
				temp = temp.next;
			}
			temp.next = newNode; //마지막 노드에 추가할 노드 넣기
		}
		count++; //노드 수 증가
		
		
		return newNode; //새로 삽입한 노드 반환
	}
	
	public MyListNode insertElement(int position, String data) {
		
		int i;
		MyListNode tempNode = head;
		MyListNode newNode = new MyListNode(data);
		
		if(position < 0 || position > count) {
			System.out.println("추가 할 위치 오류. 현재 리스트 개수 : " + count );
			return null;
		}
		
		if(position == 0) {
			//맨 앞으로 들어가는 경우
			newNode.next = head; //새로 들어갈 노드의 다음 노드는 현재 맨 앞에 있는 노드로 설정
			head = newNode; //맨 앞노드는 새로 들어갈 노드로 설정
		}else {
			//맨 앞으로 들어가는 경우가 아닌 경우
			MyListNode preNode = null; //앞 노드를 담을 변수
			for(i=0; i<position; i++) {
				preNode = tempNode; // 넣을 위치의 이전 노드를 설정 
				tempNode = tempNode.next; //임시노드에 다음 노드를 설정
			}
			newNode.next = preNode.next; //새로운 노드의 다음 노드는 이전노드의 다음노드로 설정
			preNode.next = newNode; //이전노드의 다음 노드는 새로운노드로 설정
 			
		}
		count++; //노드 수 증가
		
		return newNode; //삽입된 노드 반환
	}
	
	public MyListNode removeElement(int position) {
		
		int i ;
		MyListNode tempNode = head;
		
		if(position >= count ){
			System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return null;
		}
		
		if(position == 0){  //맨 앞을 삭제하는
			head = tempNode.next;
		}
		else {
			MyListNode preNode = null;
			for(i=0;i<position; i++) {
				preNode = tempNode;         //삭제할 위치의 이전노드 
				tempNode = tempNode.next;	//삭제할 노드 설정
			}
			preNode.next = tempNode.next; //이전 노드의 다음 노드는 삭제할 노드의 다음 노드로 설정
		}
		count--; //노드 수 1감소
		System.out.println(position + "번째 항목이 삭제되었습니다.");

		return tempNode; //삭제한 노드 반환
	}
	
	public String getElement(int position)
	{
		// 노드의 데이터 반환 메소드
		int i;
		MyListNode tempNode = head;
		
		if(position >= count ){
			//검색할 위치가 노드 수보다 크거나 같은 경우
			System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return new String("error");
		}
		
		if(position == 0){  //맨 첫번째 노드인 경우
			
			return head.getData();
		}
		
		for(i=0; i<position; i++){
			//처음부터 찾는 노드 위치의 까지 탐색 
			tempNode = tempNode.next;
			
		}
		// 찾는 노드 데이터 반환
		return tempNode.getData();
	}
	
	public MyListNode getNode(int position)
	{
		//찾는 노드 반환 메소드
		int i;
		MyListNode tempNode = head;
		
		if(position >= count ){
			System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return null;
		}
		
		if(position == 0){  //맨 첫 노드인경우

			return head;
		}
		
		for(i=0; i<position; i++){
			tempNode = tempNode.next;
			
		}
		return tempNode; //찾는 노드 반환
	}
	
	public void removeAll()
	{
		//노드 전체 삭제
		head = null;
		count = 0;
		
	}
	
	public int getSize()
	{
		//사이즈 반환
		return count;
	}
	
	public void printAll()
	{
		//전체 출력
		
		if(count == 0){
			System.out.println("출력할 내용이 없습니다.");
			return;
		}
		
		//첫 노드 부터 마지막 노드까지 출력
		MyListNode temp = head;
		
		while(temp != null){
			System.out.print(temp.getData());
			temp = temp.next;
			if(temp!=null){
				System.out.print("->");
			}
		}
		System.out.println("");
	}
	
	public boolean isEmpty()
	{
		//비었는지 체크
		if(head == null) return true;
		else return false;
	}

}

---

MyLinkedListTest.java

public class MyLinkedListTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyLinkedList list = new MyLinkedList();
		list.addElement("A");
		list.addElement("B");
		list.addElement("C");
		list.printAll();
		list.insertElement(3, "D");
		list.printAll();
		list.removeElement(0);
		list.printAll();
		list.removeElement(1);
		list.printAll();
						
		list.insertElement(0, "A-1");
		list.printAll();
		System.out.println(list.getSize());
		
		list.removeElement(0);
		list.printAll();
		System.out.println(list.getSize());
		
		list.removeAll();
		list.printAll();
		list.addElement("A");
		list.printAll();
		System.out.println(list.getElement(0));
		list.removeElement(0);

	}

}