[자료구조] 링크드리스트(LinkedList) (feat.Java예제)

public class LinkedList<E>{

	class Node<E>{
        E data;
        Node<E> next;

        public Node(E obj){
           this.data = obj;
           this.next = null;
        }
    }
    
    Node node(int index) {
    	// 첫 번째 노드부터 찾기
        Node x = head; 
        for (int i = 0; i < index; i++){
            // 첫번째 노드에서 부터 찾으려는 인덱스만큼 next해서 찾는다.
            x = x.next; 
        }
        return x;
	}

	private Node<E> head;
    private Node<E> tail;
    private int size;

	public LinkedList() {
    	head = null;
        size = 0;
    }

	public void addFirst(Object obj){
    	Node newNode = new Node(obj);
        newNode.next = head;
        head = newNode;
        size++;
        if(head.next == null){
        	tail = head;
        }
    }
    
    public void addLast(Object obj){
    	Node newNode = new Node();
        
        if(size == 0){
        	addFirst(obj);
        } else {
        	tail.next = newNode;
            tail = newNode;
            size++;
        }
    }
    
    public void add(int k, Object obj){
    	if(k == 0){
        	addFirst(obj);
        } else {
        	Node temp1 = node(k-1);
            Node temp2 = temp1.next;
            Node newNode - new Node(obj);
            temp1.next = newNode;
            newNode.next = temp2;
            size++;
            
            if(newNode.next == null){
            	tail = newNode;
            }
        }
    }
	
    public String toString(){
    	if(head == null){
        	return "[]";
        }
        
        Node temp = head;
        StringBuilder sb = "[";
        
        while(temp.next != null){
        	sb.append(temp.data + ",");
        }
        
        sb.append(temp.data + "]");
        
        return sb.toString();
    }
    
    public Object removeFirst(){
    	Node temp = head;
        head = temp.next;
        Object returnData = temp.data;
        temp = null;
        size --;
        return returnData;
    }
    
    public Object remove(int k){
    	if(k == 0){
        	return removeFirst();
        }
        
        Node temp = node(k-1);
        Node todoDeleted = temp.next;
        
        temp.next = temp.next.next;
        
        Object returnData = todoDeleted.data;
        
        if(todoDeleted == tail){
        	tail = temp;
        }
        
        todoDeleted = null;
        
        size--;
        
        return returnData;
    }
    
    public int size(){
    	return size;
    }
    
    public Object get(int k){
    	return node(k).data;
    }
    
    public int indexOf(Object data){
    	Node temp = head;
        int index = 0;
        
        while(temp.data != data){
        	temp = temp.next;
            index++;
            
            if(temp == null){
            	return -1;
            }
        }
        
        return index;
    }
}

LinkedList(연결리스트)를 Java를 통해 구현을 해봤다.

생활 코딩을 참고하여 구현을 해봤으며 그동안 이론으로만 알고 있던 내용을 손으로 직접 구현을 해보니 더욱 머리속에 잘 그려진 것 같다.

노드라는 클래스를 이용하여 첫번째, 마지막 노드를 저장하고 현재 노드의 뒤에 있는 노드만을 지정해주면 따로 인덱스를 구할 필요가 없기 때문에 더욱 빠른 수정이 가능하다.