링크드리스트

링크드 리스트 기본 정리

• 연결 리스트라고도 불린다.

• 배열은 순차적으로 연결된 공간에 데이터를 나열한다

• 링크드리스트는 떨어진 곳에 화살표를 연결하여 데이터를 나열한다고 생각하면 이해하기 좀 더 쉽다.

• 장점 : 데이터의 저장공간 낭비를 줄일 수 있지만 어떻게 보면 노드 안에 값이 2개가 들어가기 때문에 낭비 요소는 있다.

• 단점 : 접근 속도가 느리다, 중간 데이터 삭제시 이전, 다음 데이터의 연결 작업이 필요하다.

링크드리스트 기본 용어

• 노드 : 데이터의 저장 단위(데이터 값, 포인터)로 구성이 되어있다.

• 포인터 : 다음이나 이전 데이터의 노드값이 들어있다.

• * 작성해본 링크드리스트 **

public class MySingleNode<T> {

   public Node Head = null;

    public class Node<T> {
        T data;
        Node<T> pointer;

        public Node(T item) {
            this.data = item;
        }

    }

    public void addNode(T data) {
        if (Head == null) {
            Head = new Node<T>(data);
        } else {
            Node node = Head;
            while (node.pointer != null) {
                node = node.pointer;
            }
            node.pointer = new Node<T>(data);
        }
    }

    public void printAll() {
        if (Head != null) {
            Node<T> node = this.Head;
            System.out.println(node.data);
            while(node.pointer != null) {
                node = node.pointer;
                System.out.println(node.data);
            }
        }
    }

    public Node<T> search(T data) {
        if (this.Head == null) {
            return null;
        }
        else {
            Node<T> node = this.Head;
            while (node != null) {
                if (node.data == data) {
                    return node;
                } else {
                    node = node.pointer;
                }
            }
            return null;
        }
    }

    public void addNodeInside(T data, T isData) {

        Node<T> searchNode = this.search(isData);

        if (searchNode == null) {
            addNode(data);
        } else {
            Node<T> nextNode = searchNode.pointer;
            searchNode.pointer = new Node<T>(data);
            searchNode.pointer.pointer = nextNode;
        }

    }

    public void MyDeleteNodeInside(T deleteData) {
        if(this.Head == null) {
            ;
        } else {
            Node<T> node = this.Head;
            while (node != null) {
                if(node.pointer.data == deleteData) {
                    node.pointer = node.pointer.pointer;
                    break;
                } else {
                    node = node.pointer;
                }
            }
        }
    }

    public boolean delNode(T isData) {
        if (this.Head == null) {
            return false;
        } else {
            Node<T> node = this.Head;
            if (node.data == isData) {
                this.Head = this.Head.pointer;
                return true;
            } else {
                while (node.pointer != null) {
                    if (node.pointer.data == isData) {
                        node.pointer = node.pointer.pointer;
                        return true;
                    }
                    node = node.pointer;
                }
                return false;
            }
        }
    }

    public static void main(String[] args) {
        MySingleNode<Integer> myList = new MySingleNode<>();
        myList.addNode(1);
        myList.addNode(2);
        myList.addNode(3);
        myList.addNodeInside(5,2);
        myList.delNode(3);


        myList.printAll();

    }
}