Javascript 연결 목록 데이터 구조

링크드리스트:

연결된 목록은 배열과 유사한 선형 데이터 구조입니다. 그러나 배열과 달리 요소는 특정 메모리 위치나 인덱스에 저장되지 않습니다. 오히려 각 요소는 해당 목록의 다음 개체에 대한 포인터 또는 링크를 포함하는 별도의 개체입니다.

이점:
  • 전체 데이터 구조를 재구성하지 않고 연결 목록에서 노드를 쉽게 추가하거나 제거할 수 있습니다.

  • 단점:
  • 배열을 통한 연결 목록에서 검색 작업이 느리고 데이터 요소에 대한 임의 액세스가 허용되지 않습니다. 노드는 첫 번째 노드부터 순차적으로 액세스됩니다.
  • 포인터를 저장하기 때문에 배열보다 더 많은 메모리를 사용합니다.

  • 연결 리스트 내부 설계

    function LinkedList() {
        let length = 0;
        let head = null;
        const Node = function(element) {
            this.element = element;
            this.next = null;
        }
        this.size = function() {
            return length;
        }
        this.head = function() {
            return head;
        }
        this.add = function(element) {
            let node = new Node(element);
            if (head == null) {
                head = node;
            } else {
                let currentNode = head;
                while (currentNode.next) {
                    currentNode = currentNode.next;
                }
                currentNode.next = node;
            }
            length++
        }
    
        this.remove = function(element) {
            let currentNode = head;
            let previousNode;
            if (currentNode.element == element) {
                head = currentNode.next;
            } else {
                while (currentNode.element !== element) {
                    previousNode = currentNode;
                    currentNode = currentNode.next;
                }
                previousNode.next = currentNode.next;
            }
            length--;
        }
        this.isEmpty = function() {
            return length == 0;
        }
        this.indexOf = function(element) {
            let currentNode = head;
            let index = -1;
            while (currentNode) {
                index++;
                if (currentNode.element == element) {
                    return index;
                }
                currentNode = currentNode.next;
            }
            return -1;
        }
        this.elementAt = function(index) {
            let currentNode = head;
            let count = 0;
            while (count < index) {
                count++
                currentNode = currentNode.next;
            }
            return currentNode.element;
        }
    }
    var link = new LinkedList();
    link.add("hello");
    link.add("hello")
    console.log(link)
    console.log("elementAt", link.elementAt(0))
    console.log("indexOf", link.indexOf("bye"))
    link.remove("hello")
    link.remove("hello")
    console.log("isEmpty", link.isEmpty())
    console.log("length", link.size())
    


    Any comments or suggestions are welcome.

    좋은 웹페이지 즐겨찾기