4. Linked List

💻 Linked List

링크드 리스트란 연속적이지 않은 공간에 데이터를 저장한다.
노드 단위로 저장이 되며 이 노드에는 데이터와 다음 노드를 가르키는 참조자가 존재한다.

참조자를 통해 각 노드끼리 연결된다.

첫 노드의 위치를 알기위해 Header가 존재하며 시스템에 따라
마지막 노드를 알기위해 Tail을 사용하기도 한다.

<장점>
배열과 다르게 길이의 제한이 없다.
새로운 데이터가 들어올시 노드의 연결을 끊고 다시 이어주면 되기 때문이다.

또한 배열 처럼 데이터를 모두 밀거나 당길 필요 없이
바로 삭제와 추가가 가능하다.

<단점>
인덱스를 통한 조회가 불가하기 때문에 원하는 데이터를 찾기위한 시간이 오래걸린다.

---

💻 기능

Linked List도 List 객체를 상속받아 만들어진다.
따라서 ArrayList와 기본적인 기능은 비슷하며

구현또한 동일하게 할 계획이다.

포인터가 없이 저걸 어떻게 구현해야하나 싶지만 사실 방법이 있다.

📖 참조자료형

참조 자료형은 Heap영역에 동적 할당되며 동적할당 된 영역의 시작주소가
스택에 저장되는 방식이다.

즉, C에서 동적할당을 하는 것이랑 같은 방식이다.

우리가 String str=new String("어쩔티비");
를 하게되면 Heap영역에 어쩔티비 라는 문자열 상수가 저장되고

이 상수의 시작주소를 str에 복사하여 저장한다.

클래스의 경우에는

Stack (main method)          Heap
----------------------       ------------------------
| myObject (0x1a2b) | -----> | MyClass (0x1a2b)      |
|                   |        | intValue: 10          |
|                   |        | doubleValue: 20.5     |
|                   |        | stringValue: "Hello"  |
----------------------       ------------------------



위 그림처럼 스택에는 클래스의 주소가 그 내부에는 다양한 멤버변수,매소드 등이 존재한다.

---

📖 참조자료형의 Call by Value

참조자료형은 언뜻 보면 Call by Reference 방식인 것 같으나 실상은 그렇지 않다.


public class Member {
    public String name;
}

public void change(Member m) {
    m.name = "김민수";
}

라는 메소드는 Member 클래스를 받아 해당 클래스의 이름을 변경해준다.

Main에서 실행 후 결과를 보면 이름값이 바뀜을 알 수 있다.


public static void main(String[] args) {
    Member member = new Member();
    member.name = "이영희";

    change(member);

    System.out.println(member.name); // 출력 결과: "김민수"
}


이걸 보고 자바도 Call by Reference를 지원하는구나! 싶지만 실상은 그렇지 않다.

위에서 말했듯이 자바의 참조자료형은 힙에 저장되며 그 주소만 스택에 저장된다. 
우리가 매개변수를 통해 참조자료형을 넘겨줄 때 사실은 이 스택에 저장된 주소값이 복사되어 넘어가는 것이다.

따라서 이 주소값에 해당하는 클래스 내부의 name을 변경하라는 명령이기에 변경된 것이다. 

만약 메소드가

public void change(Member m) {
    m = new Member();
    m.name = "김민수";
}

이런 식으로 새로운 Member 클래스로 갈아끼우려 한다면 변화하지 않을 것이다.

📖 그림으로 설명

변경 전

Stack                    Heap
-----------------       ---------------------
| member (0x1a2b) | ---> | Member object     |
-----------------       | name: "이영희"    |
                        ---------------------

메소드 호출 시

Stack (change method)   Stack (main method)     Heap
----------------------  -----------------       ---------------------
| m (0x1a2b)          | ---> | member (0x1a2b) | ---> | Member object |
----------------------  -----------------      | name: "이영희"        |
                                                ---------------------

m.name = "김민수" 수행 후

변경 후

Stack                    Heap
-----------------       ---------------------
| member (0x1a2b) | ---> | Member object     |
-----------------       | name: "김민수"    |
                        ---------------------

---

💻 전체 구현

java에서 사용하는거 처럼 양방향 LinkedList를 구현해보자.

📖 Node

private class Node{
        //1. 데이터를 저장 가능해야함
        //2. 다음 노드를 가르켜야함 단 포인터는 없음;; 되게 불편하네
        private Object data;
        private Node nextNode;//남들은 참조 불가
        private Node prevNode;

        public Node(){
            this.data=null;
            this.nextNode=null;
            this.prevNode=null;
        }//노드 생성시 초기화

        public Node(Object input){
            this.data=input;
            this.nextNode=null;
            this.prevNode=null;
        }//값 입력시 값 반영하여 초기화

        @Override
        public String toString(){
            return String.valueOf(this.data);
        }
    }

📖 Header와 Tail

LinkedList 클래스 선언시 자동으로
Head와 Tail이 서로를 가르키게 해야함.


public class customLinkedList {
    private Node Head;
    private Node Tail;
    
     customLinkedList(){
        Head=new Node();
        Tail=new Node();

        Head.nextNode=Tail;
        Tail.prevNode=Head;
    }
}//이를 위해 생성자에 클래스 생성시 자동으로 Node를 할당받아 서로 연결하게 해줌

📖 addFirst와 addLast

1. 초기상태에서 삽입시

위와 같은 구조를 띄고 있을것이다.

이때 새로운 노드를 추가한다고 해보자.

이 구조에서 새로운 노드를 추가하기 위해서는

Head.nextNode를 newNode에 연결하고
Tail.prevNode를 newNode에 연결해야 할것이다.

즉 다음과 같은 연결을 끊고 새로 삽입을 해야한다.

여기서 더 확장을 해보자.
초기 상태에서 좀더 진행됬을 경우라고 해보자.

만약 이런식이라면? Tail은 저~~ 뒤에 존재한다면?

이경우 우리는 Head만 사용이 가능하다.
반대의 경우도 마찬가지 일 것이다.


따라서 우리는 Head와 Tail만을 사용해서 같은 효과를 내어야 한다.

초기 상태에서 Head.nextNode == anotherNode를

anotherNode.prevNode=Head를 가르키고 있다.

만약 Head.nextNode=newNode를 먼저 연결시켜버린다면
anotherNode에 대한 정보를 유실할 것이다.

따라서 우리는 anotherNode를 Head를 통해 먼저 newNode와 연결해야한다.

그 다음 Head와 newNode를 연결한다.

반대의 경우도 똑같은 원리로 anotherNode부터 연결후 Tail을 연결해야 한다.

이를 코드로 쓰면 다음과 같다.

---

구현

public void addFirst(Object obj){
        Node newNode=new Node(obj);

        Head.nextNode.prevNode=newNode;
        newNode.nextNode=Head.nextNode;//another Node부터 연결

        Head.nextNode=newNode;
        newNode.prevNode=Head;

        size++;
    }

    public void addLast(Object obj){
        Node newNode=new Node(obj);

        Tail.prevNode.nextNode=newNode;
        newNode.prevNode=Tail.prevNode;//another Node부터 연결

        Tail.prevNode=newNode;
        newNode.nextNode=Tail;

        size++;
    }

---

결과

public static void main(String[] args) {
        customLinkedList cLinkedList=new customLinkedList();

        cLinkedList.addFirst(1);
        cLinkedList.addFirst(2);
        cLinkedList.addFirst(3);
        cLinkedList.addFirst(4);
        cLinkedList.addFirst(5);

        cLinkedList.addLast(1);
        cLinkedList.addLast(2);
        cLinkedList.addLast(3);
        cLinkedList.addLast(4);
        cLinkedList.addLast(5);

        cLinkedList.printAll();
    }
    
     public void printAll(){
        int i=0;
        for(Node tmp=Head.nextNode;tmp.nextNode!=null;tmp=tmp.nextNode,i++)
            System.out.println(i+"번째 데이터"+tmp.data);
    }
    
    다음과 같이 노드를 추가하고 출력시 사진과 같은 결과가 나옴을 확인할수있다.

📖 add

원하는 위치에 데이터를 저장하는 add를 구현해보자.

이를 위해 원하는 인덱스의 해당하는 노드를 찾는 node 매소드를 구현한다.

private Node node(int index){
        if(index>size)
            return null;

        Node tmp=Head;

        for(int i=0;i<=index;i++)
            tmp=tmp.nextNode;

        return tmp;
    }//i번째 노드 반환하기 
    
이를 활용하여 add구현한다.

위에서는 index에 해당하는 노드를 반환한다.

만약 add에서 2번째 인덱스에 3을 저장하고 싶다고 한다면
현재 2번 위치의 노드는 밀려서 3번이 되고  newNode가 2번이 되어야한다.

즉, 위에서 2번을 찾은후 Tail을 연결시키듯이 똑같이 하면 된다.

구현 및 결과

public static void main(String[] args) {
        customLinkedList cLinkedList=new customLinkedList();

        cLinkedList.addFirst(1);
        cLinkedList.addFirst(2);
        cLinkedList.addFirst(3);
        cLinkedList.addFirst(4);
        cLinkedList.addFirst(5);

        cLinkedList.addLast(1);
        cLinkedList.addLast(2);
        cLinkedList.addLast(3);
        cLinkedList.addLast(4);
        cLinkedList.addLast(5);

        cLinkedList.printAll();

        cLinkedList.add(3,"어쩔티비");
        cLinkedList.printAll();

        
    }

public void add(int index,Object obj){
        Node base=node(index);
        Node newNode=new Node(obj);

        base.prevNode.nextNode=newNode;
        newNode.prevNode=base.prevNode;//another Node부터 연결

        base.prevNode=newNode;
        newNode.nextNode=base;
    }
    

https://github.com/Rachi3/dataStructure/tree/master/3.LinkedList

남은 부분 구현된 링크다.