[ 자료구조 ] LinkedList 공부

자료구조 일반적인 LinkedList 에 대해서 공부해보겠습니다. 

 

아래의 코드와 같이 연결이 되어잇는 것을 LinkedList 로 구현될 수 있습니다. 

package com.allendowney.thinkdast;
 
/**
 * @author downey
 *
 */
public class ListNode {
 
    public Object data;
    public ListNode next;
 
    public ListNode() {
        this.data = null;
        this.next = null;
    }
    
    public ListNode(Object data) {
        this.data = data;
        this.next = null;
    }
    
    public ListNode(Object data, ListNode next) {
        this.data = data;
        this.next = next;
    }
    
    public String toString() {
        return "ListNode(" + data.toString() + ")";
    }
}
 

위의 코드를 가지고 아래와 같이 실행하여

1. 노드와 [ 연결 ] 을 둘 다 수행할 수 있습니다. 

2. 혹은 노드를 먼저 생성하고 그 이후에 연결할 수 있습니다. 

 

public class LinkedListExample {    
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        
        node1.next = node2;
        node2.next = node3;
        node3.next = null;
        
        ListNode node0 = new ListNode(0, node1);
        System.out.println(node0);
        System.out.println(node1);
    }
}
 

xxxxxxxxxxxxx example xxxx

 

    @Override
    public boolean add(E element) {
        if (head == null) {
            head = new Node(element);
        } else {
            Node node = head;
            // loop until the last node
            for ( ; node.next != null; node = node.next) {}
            node.next = new Node(element);
        }
        size++;
        return true;
    }
 
    @Override
    public void add(int index, E element) {
        //TODO: FILL THIS IN!
        // this is about 
//        if (index == 0 )
//        for (int i index ) 
        
        if ( index == 0) {
            head = new Node(element); // first node insertion
            
//            for( ; he) // other nodes should be going to change their index
        }    
        else {
            Node node = head;
            
            for (; node.next != null ; node = node.next) {
                node.next = new Node(element);
            }
        }
        
        size++;
        
    }

xxxxxxxxxxxxx example xxxx

 

    private Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node node = head;
        for (int i=0; i<index; i++) {
            node = node.next;
        }
        return node;
    }
 
    @Override
    public int indexOf(Object target) {
        //TODO: FILL THIS IN!
        Node node = head;
        
        for (int i = 0; i<size ; i++) {
            if( target == node) 
                return i;
            
            node = node.next;
        }
        
//        
        return -1;
    }
 
 
    @Override
    public boolean remove(Object obj) {
        int index = indexOf(obj);
        if (index == -1) {
            return false;
        }
        remove(index);
        return true;
    }
 
    @Override
    public E remove(int index) {
        //TODO: FILL THIS IN!
//        //remove connection 
//        Node node = head;
 
        
        Node node = this.getNode(index);
        node = null;
        if( index != 0) {
            Node prevNode = this.getNode(index-1);
            Node nextNode = this.getNode(index+1);
            prevNode.next = nextNode;
        }
        else {
            //head node setting 
            Node nextNode = this.getNode(index+1);
            this.head = nextNode;
        }
        
        size--;
        
        
        return null;
    }