리스트

리스트는 데이터를 순서대로 나열한 자료구조 입니다. 그 중에서도 가장 간단한 구조를 선형 리스트또는 연결 리스트라고도 합니다. 

메모리 주소를 통해 데이터를 관리한다.

선형 리스트는 배열 또는 포인터로 구현 가능 하지만 배열로 구현하는건 별로 추천드리지 않습니다.

• 쌓이는 데이터의 크기를 미리 알아야 한다.
• 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않다.

이 두가지가 커다란 단점이기 때문이죠. 그래서 포인터로 구현하는 선형 리스트를 알아보겠습니다.

import java.util.Comparator;

public class LinkedList <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> crnt;       //선택노드
    
    public LinkedList(){
        head = crnt = null;
    }
    
    public E search(E obj, Comparator<? super E> c){
        Node<E> ptr = head;
        
        while(ptr != null){
            if(c.compare(obj, ptr.data)== 0){
                crnt = ptr;
                return ptr.data;
            }
            ptr = ptr.next;
        }
        return null;
    }
    
    public void addFirst(E obj){
        Node<E> ptr = head;
        head = crnt = new Node<E>(obj, ptr);
    }
    
    public void addLast(E obj){
        if(head == null)
            addFirst(obj);
        else{
            Node<E> ptr = head;
            while(ptr.next != null)
                ptr = ptr.next;
            ptr.next = crnt = new Node<E>(obj, null);
        }
    }
    
    public void removeFirst(){
        if(head != null)
            head = crnt = head.next;
    }
    
    public void removeLast(){
        if(head != null){
            if(head.next == null)
                removeFirst();
            else{
                Node<E> ptr = head;
                Node<E> pre = head;
                
                while(ptr.next != null){
                    pre = ptr;
                    ptr = ptr.next;
                }
                pre.next = null;
                crnt = pre;
            }
        }
    }
    
    public void remove(Node p){
        if(head != null){
            if(p == head)
                removeFirst();
            else{
                Node<E> ptr = head;
                
                while(ptr.next != p){
                    ptr = ptr.next;
                    if(ptr== null) return;
                }
                ptr.next = p.next;
                crnt = ptr;
            }
        }
    }
    
    public void removeCurrentNode(){
        remove(crnt);
    }
    
    public void clear(){
        while(head != null)
            removeFirst();
        crnt = null;
    }
    
    public boolean next(){
        if(crnt == null || crnt.next == null)
            return false;
        crnt = crnt.next;
        return true;
    }
    
    public void printCurrentNode(){
        if(crnt == null)
            System.out.println("선택한 노드가 없습니다.");
        else
            System.out.println(crnt.data);
    }
    
    public void dump(){
        Node<E> ptr = head;
        
        while(ptr != null){
            System.out.println(ptr.data);
            ptr = ptr.next;
        }
    }
}

삭제, 삽입, 출력등의 메소드를 구현한 링크드 리스트 입니다.