자료구조(Linked list) 구현

Array list: 다닥다닥 연속적으로 붙어있음

Linked list: 서로 연결되어 있지만, 떨어져있음

 

LINKED LIST 구조

데이터와 다음노드가 무엇인가?를 저장한다.

헤드필드를 찾아야 다음 연결된 노드를 찾을 수 있다.

 

일단 구조에대해서 알아야할 필요가 있다.

linkedlist는 data, linkedfeild(연결), head, tail로 구성되어있다.

이것들을 이용하여 생성, 삽입, 삭제 등이 가능하다.

 

이와같이 collection이 있다.

아직 배우지 못한 set과 queue와 map은 linkedlist와 doublylinkedlist를 배운 후 

보도록 한다.

 

맨 앞으로 집어 넣기 (30) -> (20)-(30) -> (10)-(20)-(30) .....

package list.linkedlist.implementation;

public class Main {

    public static void main(String[] args) {
	    Linkedlist numbers = new Linkedlist();
	    numbers.addFirst(30);
        numbers.addFirst(20);
        numbers.addFirst(10);
        numbers.addFirst(5);

        System.out.println(numbers.toString());
    }

}

package list.linkedlist.implementation;

public class Linkedlist {
    //누가 머리인가
    private Node head;
    //누가 꼬리인가
    private Node tail;
    //사이즈는?
    private int size = 0;

    //한개의 노드에 뭐가 들어갈지 클래스를 정의해줌
    private class Node{
        private Object data;
        //다음의 노드를 정의해줄때, 그 노드(엘리먼트)의 데이터타입
        private Node next;
        //노드를 생성할때 그 노드는 값을 가지고 있어야 삽입,삭제,변경이가능
        public Node(Object input){
            this.data = input;
            this.next = null;
        }
        //print할때 스트링으로 좀 볼라규~
        public String toString(){
            return String.valueOf(this.data);
        }
        //위의 Node클래스를 new로 생성해 객체화 시키고
        //생성자(즉, 초기값 data, next가 들어가야할)를 이용해 값을 넣어준다.

    }
    public void addFirst(Object input){
        Node newNode = new Node(input);
        newNode.next = head;
        head = newNode;
        size++;
        if(newNode.next == null){
            tail = head;
        }
    }
}

맨 뒤로 집어 넣기 (20) -> (20)-(10) -> (20)-(10)-(5) .....

package list.linkedlist.implementation;

public class Main {

    public static void main(String[] args) {
	    Linkedlist numbers = new Linkedlist();
        numbers.addLast(20);
        numbers.addLast(10);
        numbers.addLast(5);

        System.out.println(numbers.toString());
    }

}

  public void addLast(Object input){
          Node newNode = new Node(input);
          if(size ==0){
              addFirst(input); //아무것도 없으면 addFirst로 값을 넣어주고
          }else{
              tail.next = newNode; //있으면 기존의 마지막의 다음이 새로만든게 되는거고
              tail = newNode; //순서를 정해줬으면 못을 박아준다.
              size++; //추가됐으니 사이즈 하나 업해주고~
          }
    }

 

원하는 곳에 추가하기

 

    //내부적으로 인덱스값을 주면 엘리멘트 값을 받기 위한 node 메소드
    Node node(int index){
        Node x = head;
        for(int i=0; index > i; i++){
            x = x.next;
        }
        return x;
    }
    public void add(int k,Object input){
        if(k == 0){
            addFirst(input);
        } else{
            Node temp1 = node(k-1); //1번값 0-0(<-여기다가 넣고싶으면)-0 그전의 값을 알아야함
            Node temp2 = temp1.next; //2번값
            Node newNode = new Node(input);  //2번값이 되고 싶은 값
            temp1.next = newNode;
            newNode.next = temp2;
            size++;

        }
    }

string 구현

 package list.linkedlist.implementation;

public class Main {

    public static void main(String[] args) {
	    Linkedlist numbers = new Linkedlist();
        numbers.addLast(20);
        numbers.addLast(10);
        numbers.addLast(5);

        System.out.println(numbers.toString());
    }

}
    
    

    
    ---------------------------------------------------------
    
    //toSTring 구현
    public String toString(){
        Node temp = head; //먼저 머리값을 구해줌
        String str = "["; //가장 앞 스트링
        while (temp.next != null){ //헤드의 다음 노드가 없을때까지
            str += temp.data + ", "; //스트링 변수에 담아줌
            temp = temp.next; //다음 노드를 불러옴
        }
        str += temp.data; //마지막 노드 , <-를 빼주기 위해

        return str+ "]";
    }
    
    출력
    [20, 10, 5]

 맨 앞의 데이터 지우기

package list.linkedlist.implementation;

public class Main {

    public static void main(String[] args) {
	    Linkedlist numbers = new Linkedlist();
        numbers.addLast(20);
        numbers.addLast(10);
        numbers.addLast(5);

        System.out.println(numbers.removeFirst());
    }

}
--------------------------------------------------------------------
    //첫번째 노드 삭제
    public Object removeFirst() {
        Node temp = head;
        head = temp.next;
        Object returnData = temp.data; //데이터값을 리턴시키기위해
        temp = null; //
        size--;
        return returnData;
    }

출력
20

 

원하는 노드, 마지막 노드 삭제

 

//원하는 노드 삭제
    public Object remove(int k){
        if(k == 0) {
            return removeFirst();
        }else{
            Node temp = node(k-1);
            Node todoDeleted = temp.next;
            Node temp3 = node(k+1);
            temp.next = temp3;
            Object returnData = todoDeleted.data;
            if(todoDeleted == tail){ //만약 지워할 것이 마지막이었다면 그 앞에 노드를 꼬리로 지정
                tail = temp;
            }
            todoDeleted = null;
            size--;
            return returnData;
        }
    }
    //마지막 노드 삭제
    public Object removeLast(){
        return remove(size-1);
    }

SIZE값 가져오기, GET메소드

 

    public int size(){
        return size;
    }

    public Object get(int k){
        Node temp = node(k);
        return temp.data;
    }

인덱스 출력하기

    public int indexOf(Object O){
        Node temp = head;
        int index = 0;
        while(temp.data != O){ //내가 찾으려는 것과 값이 다르다면
            temp = temp.next; // head.next가 다음 temp의 자리로오고
            index++; // 인덱스도 하나 +
            if(temp == null){
                return -1;
            }
        }
        return index;
    }

Iterator 반복문 만들기

 //Iterator
    public ListIterator listIterator(){
        return new ListIterator();
    }

    public class ListIterator{
        private Node next;
        private Node lastReturned;
        private int nextIndex;
        ListIterator(){ //초기화
            next = head;
        }
        public Object next(){
            lastReturned = next; //값을 저장
            next = next.next; // 다음 값을 지정
            nextIndex++; // 인덱스 +1
            return lastReturned.data;
        }
        public boolean hasNext(){
            return nextIndex < size();
        }
    }

Linkedlist.ListIterator i = numbers.listIterator();

        while (i.hasNext()){
            System.out.println(i.next());
        }
        
        출력
        20
        10
        5

Linkedlist 보다 doubleList가  메모리를 더 사용한다.!

 

중간에 데이터를 낑겨넣기

 

public void add(Object data){
            Node newNode = new Node(data); //추가할거니까 새로운 노드 만들기

            if(lastReturned == null){
                head = newNode;
                newNode.next = next;
            } else{
                lastReturned.next = newNode;
                newNode.next = next;
            }
            lastReturned = newNode;
            size++;
            nextIndex++;
        }

만약, 맨 앞에 값을 추가 한다고 하면,

lastReturned는 아직 존재 하지 않을것이다. 

1. 새로운 노드를 만든 후,  조건문을 작성한 뒤, 헤드에 새로만든 노드를 넣어준다.

2. 그리고 새로운노드의 다음이 next변수가 될 것이다.

 

만약, 추가하고 싶은 곳에 추가를 하고 싶다면

1. lastReturned의 다음에 새로운 노드를 연결해준다.

2. 그리고 새로운노드의 다음이 next변수가 될 것이다.