자바의 LinkedList

데이터 구조란 무엇입니까?

데이터 구조는 데이터를 효과적으로 저장, 구성/관리 및 검색하는 방법입니다. 데이터 구조는 거의 모든 프로그램에서 사용되며 소프트웨어 엔지니어링에서 배우고 이해하는 데 매우 중요합니다.

LinkedList란 무엇입니까?

LinkedList는 종종 노드라고 하는 동일한 유형의 요소 시퀀스를 나타내는 선형(O(n)) 데이터 구조입니다. 각 노드에는 인접 및/또는 이전 노드를 가리키는 데이터 및 포인터가 있습니다. 목록의 첫 번째 노드를 헤드라고 하며 목록의 마지막 노드 포인터는 null 또는 헤드를 가리킵니다(Circular LinkedList). 이 데이터 구조는 동적이므로 LinkedList에서 삽입 및 삭제된 요소 수에 따라 확장 및 축소될 수 있습니다.

LinkedList를 순회하려면 처음(헤드)에서 시작하여 원하는 노드에 도달할 때까지 각 항목을 통과해야 합니다. LinkedList는 임의 액세스를 허용하지 않습니다.

Java에서 LinkedList는 Serializable, Cloneable, Iterable, Collection, Deque, List, Queue 인터페이스를 구현합니다. 이는 LinkedList 데이터 구조의 작업 및 프로그램 내에서의 사용에 있어 유연성을 제공하기 때문에 중요합니다.

아래에서는 LinkedList(Singly) 및 일부 작업을 빌드하는 방법을 보여줍니다. 그러나 구현은 문서의 구현만큼 구체적이지 않습니다. documentation 을 보려면 여기를 클릭하십시오.

구현

단일 연결 목록

Singly LinkedList에는 다음 노드의 메모리 주소를 가리키는 각 노드에 대한 포인터가 하나만 있습니다. (아래 참조)

/**
 * @author brittcodes
 *
 */
public class SinglyLinkedList {

    Node head;

    static class Node {

        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
            next = null;
        }

        public String toString() {
            return "Node [ data=" + data + ", next=" + next + " ]";
        }

    }






    /**
     * Inserts Node at the end of the list
     * 
     * @param data, primitive data type int
     */
    public void add(int data) {
        //create a new node, put data in it
        Node newNode = new Node(data);



        //if head is null, set new node as head
        if(head == null) {
            head = newNode;
            return;
        }

        //set new node next to null
        newNode.next = null;

        //find the node with next as null, and set that node to the new node
        Node last = head;
        while(last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }







    /**
     * Inserts a new Node after a given previous Node
     * 
     * 
     * @param data, primitive data type int
     */
    public void insertAfter(Node node, int data) {
        //create a new node, put data in it
        Node newNode = new Node(data);

        //set newNode's next to node's next
        newNode.next = node.next;

        //set node's next to new Node
        node.next = newNode;

                //if list is empty, set newNode to head
        if(head == null) {
            newNode = head;
        }
    }







    /**
     * Inserts a new Node at beginning of list
     * 
     * 
     * @param data, primitive data type int
     */
    public void insertToFront(int data) {

        // create a node, put data in it
        Node newNode = new Node(data);

        // set new node's pointer to the head
        newNode.next = head;

        // if list is empty, set newNode to head
        if (head == null) {
            newNode = head;
        }

        // make newNode the head
        head = newNode;

    }






    /**
     * Prints out the LinkedList
     * 
     */
    public void printList() {
        // traverse the nodes and print

        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
        System.out.println();
    }






    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        list.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        list.head.next = second;
        second.next = third;
        list.insertToFront(6);
        list.printList();
        list.insertAfter(third, 8);
        list.printList();
        list.add(23);
        list.printList();
    }

}

이중 연결 목록

Doubly LinkedList에는 각 노드에 대한 두 개의 포인터가 있습니다. 이전 노드의 메모리 주소를 가리키는 포인터 하나와 다음/인접 노드의 메모리 주소를 가리키는 다른 포인터.

/**
 * @author brittcodes
 *
 */
public class DoublyLinkedList {

    Node head;

    static class Node {
        int data;
        Node next;
        Node previous;

        public Node(int data) {
            this.data = data;
            next = null;
            previous = null;
        }

        public String toString() {
            return "Node [ data=" + data + ", next=" + next + " ]";
        }
    }








    /**
     * Prints list forwards and backwards
     * 
     * @param n, represents Node
     */
    public void printList(Node n) {

        Node last = null;

        // Prints forward
        System.out.println("\nTraverse forward");
        while (n != null) {
            System.out.print(n.data + " ");
            last = n;
            n = n.next;
        }

        // Prints backwards
        System.out.println("\nTraverse backward");
        while (last != null) {
            System.out.print(last.data + " ");
            last = last.previous;
        }

    }









    /**
     * Inserts Node to the beginning of list
     * 
     * @param data, primitive data type int
     */
    public void insertToFront(int data) {

        // create a new Node
        // put in the data
        Node newNode = new Node(data);

        // Make next of new node as head and previous as NULL
        newNode.next = head;
        newNode.previous = null;

        // change previous of head node to new node
        if (head != null) {
            head.previous = newNode;
        }

        // move the head to point to the new node
        head = newNode;

    }







    /**
     * Inserts element after specified prevNode with data at the end of the list
     * 
     * @param prevNode
     * @param data
     */
    public void insertAfter(Node prevNode, int data) {

        if (prevNode == null) {
            System.out.println("The given previous node cannot be NULL ");
            return;
        }

        Node newNode = new Node(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;

        newNode.previous = prevNode;

        if (newNode.next != null) {
            newNode.next.previous = newNode;
        }

    }

    public void insertBefore(Node node, int data) {

        Node newNode = new Node(data);

        if ((head == null) && (node == null)) {
            head = newNode;
        }

        newNode.previous = node.previous;

        node.previous = newNode;

        newNode.next = node;

        if (newNode.previous != null) {
            newNode.previous.next = newNode;
        }
    }









    /**
     * Inserts element at the end of the list
     * 
     * @param data
     */
    public void insertAtEnd(int data) {

        // create a new Node
        // put in the data
        // make new Node next point to null
        // traverse list until at last node
        // make new Node previous point to last Node
        // make last node next point to new Node

        Node newNode = new Node(data);
        Node last = head;
        newNode.next = null;

        if (head == null) {
            head = newNode;
            newNode.previous = null;
            return;
        }

        while (last.next != null) {
            last = last.next;
        }

        newNode.previous = last;
        last.next = newNode;

    }









    public static void main(String[] args) {
        DoublyLinkedList doubly = new DoublyLinkedList();

        doubly.head = new Node(4);
        Node second = new Node(5);
        Node third = new Node(6);

        doubly.head.next = second;
        second.next = third;

        third.previous = second;
        second.previous = doubly.head;

        doubly.printList(doubly.head);
        doubly.insertAfter(doubly.head, 10);
        doubly.printList(doubly.head);
        doubly.insertAtEnd(25);
        doubly.printList(doubly.head);
        doubly.insertBefore(second, 101);
        doubly.printList(doubly.head);

    }

}