링크드 리스트(1)

1) 링크드 리스트 특징

- 링크드 리스트는 하나의 저장된 데이터가 있을 때마다, 

  해당 데이터를 저장할 공간과

  다음 연결될 데이터의 주소값을 가지는 공간을 생성함  

 

- 데이터가 1000개, 2000개, 10000개가 있어도 연결해서 놓을 수 있음  

 

2) 링크드 리스트의 장단점

(1) 장점

- 미리 데이터 공간을 할당하지 않아도 됨

-> 데이터 공간이 필요할 때 할당하면 됨  

 

(2) 단점

- 항상 데이터를 저장할 때, 데이터 공간과

  다음 데이터 공간을 가리키는 데이터 공간이 필요함

-> 저장공간 효율이 높지 않음  

 

- 링크드 리스트는 데이터를 찾으려면 무조건 맨 앞부터 찾아가야 함

-> 접근 속도가 느림

 

- 중간에 있는 데이터를 삭제하려면, 부가적인 작업이 필요함 

 

 

3) 링크드 리스트 구성

- 링크드 리스트는 하나의 작업을 저장할 때, 데이터+다음 데이터의 주소가 있음

-> 그 세트를 노드라고 함

-> 다음 데이터 주소를 가리키는 공간을 포인터라고 함

-> 즉, 노드는 데이터값+포인터로 구성됨  

public class Node<T>{

   T data;
   Node<T> next = null;
   
   public Node(T data){
     this.data = data;
   }
}

 

- 단일 링크드 리스트(Single Linked List)클래스는 다음과 같이 선언할 수 있음 

public class SingleLinkedList<T>{

   public Node<T> head = null;
   
   public class Node<T>{
      T data;
      Node<T> next = null;
      
      public Node(T data){
        this.data = data;
      }
   }    
      
   public void addNode(T data){
      if(head == null){
         head = new Node<T>(data);
      }else{
         Node<T> node = this.head;
           
         while(node.next != null){
           node = node.next;
         }
         
         node.next = new Node<T>(data);
      }
   }
   
   public void printAll(){
     if(head != null){
        Node<T> node = this.head;
        System.out.println(node.data);
        while(node.next != null){
           node = node.next;
           System.out.println(node.data);
        }
     }
   }
   
 }

참고

- 한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online편