[자료 구조] 6. 연결 리스트

[자료 구조] 6. 연결 리스트

1. 연결 리스트(Linked List)란?

2. 연결 리스트 구현하기

---

 

1. 연결 리스트(Linked List)란?

-연결 리스트는 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조를 말한다.

-자료를 저장하는 노드에는, 본인의 자료와 다음 요소를 가리키는 링크(포인터)가 있다.

-자료가 추가될 때, 노드 만큼의 메모리를 할당 받고, 이전 노드의 링크로 연결한다.

(정해진 크기가 없다.)

-검색할 때에는 배열이 더욱 빠르지만, 데이터를 추가하거나, 삭제 할 때에는 연결 리스트가 더욱 용이하다.

 

*jdk 클래스: LinkedList

---

2. 연결 리스트 구현하기

-하나의 요소를 저장하는 기능 설계

 

*자기 참조(셀프 참조, Self Reference): 객체가 자신과 같은 타입의 다른 객체를 가리키는 경우를 말한다. 

연결 리스트, 트리 구조에 많이 활용된다.

 

package Structure.ch04;

public class Node {
	
	private String data;
	// 셀프 참조 = 자기 참조
    // 자기 참조는 객체가 자신과 같은 타입의 다른 객체를 
	// 가리키는 경우를 말합니다.
	// 용도 : 연결 리스트, 트리 구조에 많이 활용 됩니다.
	public Node next;


	public Node() {
		data = null;
		next = null;
	}
	
	public Node(String data) {
		this.data = data;
		next = null;
	}
	
	public Node(String data, Node link) {
		this.data = data;
		next = link;
	}
	
	public String getData() {
		return data;
	}
	
}

package Structure.ch04;

import java.util.LinkedList;

public class MyLinkedList {
	
	private Node head; // 요소의 맨 처음을 가리킴
	private int count; // 링크드 리스트의 몇 개의 요소가 연결되어 있는 갯수
	
	// MyLinkedList 맨 처음 생성시, 노드는 없는 상태이다.
	 public MyLinkedList() {
		head = null;
		count = 0;
	}
	
	 // 저장된 노드의 갯수를 반환하는 메서드
	 public int getCount() {
		 return count;
	 }
	 
	 // 새로운 노드(Node Class)를 한 개 추가하는 메서드를 만들자.
	 public Node addElement(String data) {
		 Node createNode = new Node(data);
		 if(head == null) {
			 // 맨 처음 요소를 저장하는 동작
			 head = createNode;
		 } else {
			 // 항상 요소 찾기는 head에서부터 시작!
			 Node preNode = head;                                    
			 while(preNode.next!= null ) {
				 preNode = preNode.next;
			 }
			 // 핵심 코드
			 preNode.next = createNode;
		 }
		 count++;
		 return createNode; // 추후 수정
	 } // end of class
	 
	 public Node removeElement(int index) {
		 // 방어적 코드 작성                         
		 // 0,1
		 if(index >= count) {
			 System.out.println("삭제할 위치 오류. 현재 리스트 갯수는 "+count+"개 입니다.");
			 return null;
		 } 
		 
		 // 맨 앞 요소를 삭제 요청 시
		 // 항상 요소를 찾을 때 시작은 head 부터 시작이다.
		 
		 Node tempNode = head;
		 if(index == 0) {
			 // 코드 시작 전 모습
			 // [야스오][티모. 주소값] --> [티모][null]
			 head = tempNode.next;
			 // 코드 수행 후 모습
			 // [티모][null]
		 } else {
			 // 코드 시작 전 모습 : position -> 2이라고 가정 -> n-1 -> 1
			 // [야스오][티모. 주소값] --> [티모][소라카. 주소값] -->[소라카][null]
			 Node preNode = null;
			 for(int i = 0; i < index; i++) {
				 preNode = tempNode;
				 tempNode = tempNode.next;
			 }
			 preNode.next=tempNode.next;
			 
		 } // end of if
		 count--;
		 System.out.println(index + " 번째 요소를 삭제 했습니다.");
		 return tempNode; // 추후 수정
	 }
	 
	 // 전체 출력 하는 기능 만들기
	 public void printAll() {
		 if(count == 0) {
			 System.out.println("출력할 내용이 없습니다.");
			 return;
		 }
		 
		 Node temp = head;
		 while(temp != null) {
			 System.out.print(temp.getData()); 
			 temp = temp.next;
			 if(temp != null) {
				 System.out.print("-->");
			 }
		 }
		 System.out.println();
	 }
	 
	 // 지정한 위치의 노드 하나만 출력 하기
	 public Node getNodeByIndex(int index) {
		 if(index >= count) {
			 System.out.println("검색 위치 오류 - 잘못된 요청");
		 }
		 
		 Node tempNode = head;
		 if(index == 0) {
			 return head;
		 }
		 
		 for(int i=0; i==index; i++) {
			 tempNode=tempNode.next; // 다음 요소
		 }
		 
		 return tempNode;
	 }
	 
	 // 전체 삭제 기능 구현
	 public void removeAll() {
		 head =null;
		 count=0;
		 }
	 
	 
	 // 테스트 코드
	 public static void main(String[] args) {
		MyLinkedList linkedList = new MyLinkedList();
		linkedList.addElement("야스오");
		linkedList.addElement("티모");
		linkedList.addElement("소라카");
		
		linkedList.printAll();
		linkedList.removeElement(1);
		linkedList.printAll();
		// [야스오][] --> [티모][] --> [소라카][]
		
		System.out.println(linkedList.getCount());
		
		System.out.println(linkedList.getNodeByIndex(1).getData());
		
		linkedList.removeAll();
		linkedList.printAll();
	}
	 
} // end of class