더블 체인 테이블의 자바스크립트와 파이썬 구현

무엇이 쌍사슬시계입니까?

1절의 정의에서 우리는 체인 시계가 무엇인지 이미 알고 있다.쌍사슬표는 정의와 기능상 여전히 SLL(단사슬표)과 같고 유일한 차이점은 DLL(쌍사슬표)이 노드에 부가된prev 속성을 가지고 있기 때문에 앞뒤로 되돌아갈 수 있다는 것이다.

간단하게 보기 위해서, 나는 이전 절의 코드를 복제하고, 이전 속성을 포함하도록 조정했다.이 밖에 모든 조작 중의 절차는 약간의 조정이 필요하다.이제 시작하겠습니다.

우리가 실행할 행동

//를 눌러 노드 a를 끝에 추가

팝업//끝 노드 삭제

shift//시작 노드 삭제

위치 이동 취소//처음에 노드 추가

획득//특정 인덱스 또는 표준에 따라 노드 획득

설정//노드 값 속성 변경

삽입/

뜯기

반전//반전 목록의 방향

주의: 다음은 모든 함수나 방법의 실현에 대해 깊이 있게 연구하였다.모든 함수나 방법은 클래스에 있습니다: 마지막으로 전체 코드 구현을 보고 되돌아와 계속 실행합니다
시작합시다.ps:저는 자바스크립트와 파이톤에서 실현할 것입니다.

밀다

push 기능에서, 목록의 끝에 노드를 항상 추가합니다.다음은 따라야 할 절차를 개술하였다.

Step 1 - Create a newNode with given value and newNode → next as NULL.
Step 2 - Check whether list is Empty (head == NULL).
Step 3 - If it is Empty then, set head = newNode.
Step 4 - If it is Not Empty then point the tails next attribute to the newNode
step 5 - set the newNode's prev property to the current tail node
Step 6 - then reset the tail to point to the newNode and increment the size

JavaScript의 코드 구현:

class Node{
    constructor(val){
        this.val= val
        this.prev = null
        this.next=null

    }
}

class DLL{
    constructor(){
        this.head= null
        this.tail= null
        this.size= 0

    }

    push(val){
        let newNode= new Node(val);
        if(!this.head){
            this.head=newNode
            this.tail= newNode
            this.size++
            return this
        }
        this.tail.next = newNode
        newNode.prev =this.tail
        this.tail = newNode
        this.size++
        return this
    }
}

let list =new DLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)

python에서 다음을 수행합니다.

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None


class DLL:
    def __init__(self):
        self.head=None
        self.tail= None
        self.size=0

    def traverse_list(self):
        if(self.head is None):
            print("No elements in this list")
            return
        else:
            n = self.head
            while n is not None:
                print(n.val)
                n = n.next


    def push(self,val):
        newNode =  Node(val)

        if(self.head == None):
            self.head = newNode
            self.tail = newNode
            self.size+=1
            return self
        self.tail.next= newNode
        newNode.prev = self.tail
        self.tail = newNode
        self.size+=1
        return self
list = DLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
list.traverse_list()

팝송 팝송

pop 함수에서, 이것은 처음부터 끝까지 제거됩니다.다음은 따를 순서입니다.

step 1 - Handle the edge case if the list is empty return None or undefined
step 2 - Create a temp and set it to the tail node
step 3 - If the size property is equal to 1 set the head and tail properties to null
step 4 - Set the tail attribute equal to the current tails prev attribute. Also, set the tail's next property to null and the temp variable's prev property to null.
step 5 - return the list

Javascript의 코드 구현:

pop(){
        if(!this.head) return undefined;
        let temp = this.tail
        if(this.size ===1){
            this.head = null;
            this.tail = null;
        }else{
        this.tail= this.tail.prev;
        this.tail.next= null;
        temp.prev = null
        }
        this.size--;

        return this
    }

python에서 다음을 수행합니다.

def pop(self):
        if self.head ==None:return
        temp = self.tail
        if self.size == 1:
            self.head = None
            self.tail = None
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None 
        self.size-=1

        return self

옮기다

이것은 목록의 첫 번째 노드를 삭제하는 것과 관련이 있습니다.
따라야 할 단계는 다음과 같습니다.

step 1: Check if the head exists otherwise return early
step 2: Initiate a variable called temp set it equal to the head property
step 3: If the size property is one the set the head and tail property to null or None
step 4: Otherwise set the head property to be the current heads next property
step 5: Set the current head's prev property to null
step 6: decrement the size by 1
step 6: Return the list

Javascript의 코드 구현:

shift(){
       if(!this.head) return undefined
       let temp = this.head
       if(this.size ===1){
           this.head = null
           this.tail =null
       }else
       this.head = this.head.next;
       this.head.prev = null;
       }
       this.size --

       return temp
   }

python에서 다음을 수행합니다.

def shift(self):
        if self.head == None: return 
        temp = self.head
        if(self.size == 1):
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
        self.size-=1

        return temp

위치 이동 취소

이름 unshift 에서shift와 반대로, 시작에 노드 a를 추가해야 한다는 것을 알 수 있습니다.다음 절차를 따르십시오.

step 1: Create a variable newNode and instantiate the Node class will the val passed in.
step 2: If there is no head property set the head property and tail property equal to the newNode
step 3: if there is a head property set the newNodes's next property to the head property, set the head's prev property to the newNode and then set the head property to the newNode
step 4: Increment the size by 1 and return the list

Javascript의 코드 구현:

 unshift(val){
       let newNode = new Node(val);
       if(!this.head){
           this.head= newNode;
           this.tail = newNode;
       }else{
           newNode.next = this.head;
           this.head.prev = newNode;
           this.head = newNode;
       }
       this.size++;
       return this;


   }

python에서 다음을 수행합니다.

def unshift(self,val):
        newNode = Node(val)
        if self.head == None:
            self.head = newNode
            self.tail = newNode
        else:
            newNode.next = self.head
            self.head.prev = newNode
            self.head = newNode
        self.size+=1
        return self

얻다

Get 방법은 노드의 색인이나 값을 사용할 수 있는 노드의 검색 조건일 뿐이지만, 이 예에서는 색인만 사용합니다.이를 통해 스트리밍 횟수를 절반으로 줄일 수 있다.만약 색인이 목록 크기의 절반보다 크다면, 목록의 끝에 가깝다고 가정하면, 끝에서부터 검색하는 것이 더 의미가 있고, 반대로 색인이 목록 크기의 절반보다 작다면.다음 단계를 따르십시오.

step 1: If the index is less than 0 or greater than or equal to the size property return early
step 2: if index > (size/2) then we set the count to the size property minus one, set the current variable to tail node and start a while loop as long as count is not equal to index, setting current to the current's prev node and decrementing count by one each time
step 2: if index <= (size/2) then we set the count variable to zero, set the current variable to head property, and start a while loop as long as the count is not equal to index, setting current to the current's next node and incrementing count by one each time
step 4: when the loop breaks return current node

Javascript의 코드 구현:

  get(index){
       if(index<0 || index >= this.size)return undefined;
       if(index>Math.floor(this.size/2)){
       let count=this.size -1;
       let current= this.tail;
       while(count !== index){
           current= current.prev;
           count--
       }
        }else{
        let count =0;
        let current = this.head
        while(count !== index){
           current= current.next;
           count++
       }

        }

       return current;


   }

python에서 다음을 수행합니다.

def get(self,index):
        if index <0 or index >=self.size:return
        if index > math.floor(self.size/2):      
            current= self.tail
            count = self.size -1
            while count != index:       
                current = current.next
                count-=1
        else:
            current= self.head
            count = 0
            while count != index:   
                current = current.next
                count+=1
        return current

설정

이 방법은 Get 방법을 사용하여 우리가 원하는 노드를 찾고value 속성을 다른 속성으로 설정합니다.다음 절차를 따르십시오.

step 1 : Create a node variable set it to the function get with index passed in as a parameter
step 2 : If the node variable is set to a Non-null or Non- None value set the val property of the node to the new val then return true otherwise return false

Javascript의 코드 구현:

  set(index, val){
        let node = this.get(index);
        if(node){
            node.val = val;
            return true;
        }
        return false;
   }

python에서 다음을 수행합니다.

def set(self,index,val):
        node = self.get(index)
        if node :
            node.val = val
            return True
        return False

삽입

이 메서드는 특정 점에 노드를 삽입하고 Get 메서드를 보조 메서드로 사용하여 노드를 삽입할 위치를 결정합니다.다음 절차를 따르십시오.

Step 1: If the index parameter is less than zero or greater than the size property return early
step 2: if the index parameter is equal to zero, then return the unshift method with the val parameter passed in
step 3: if the index is equal to the size property return the push method with the val parameter passed in
step 4: Create a variable newNode and instantiate the Node class will the value passed in.
step 5: Get the node at the index -1 position
step 6: Create a nextNode's variable and set it equal to the current node's next property
step 7: set the current node's next property to the newNode and the newNodes's prev property to the node variable, set the newNode's next property to the nextNode and the nextNodes's prev property to the newNode
step 8: Increment the size property by 1 and return the list

Javascript의 코드 구현:

insert(index, val){
       if(index<0 || index > this.size ) return undefined
       if(index === 0){
           this.unshift(val);
       }else if(index === this.size){
           this.push(val);
       }else{
           let newNode = new Node(val);
           let node  = this.get(index-1);
           let nextNode = node.next;
           node.next = newNode, newNode.prev = node;
           newNode.next = nextNode, nextNode.prev = newNode;
       }

      this.size++;
      return this;

   }

python에서 다음을 수행합니다.

def insert(self,index, val):
        if index<0 or index> self.size: return
        if index == 0: return self.unshift(val)
        if index == self.size: return self.push(val)
        newNode = Node(val)
        prevNode = self.get(index-1)
        nextNode = prevNode.next
        prevNode.next = newNode 
        newNode.prev= prevNode
        newNode.next = nextNode 
        nextNode.prev = newNode
        self.size+=1
        return self

제거

이 방법은 목록에서 요소를 삭제합니다.다음 단계는 다음과 같습니다.

Step 1: If the index parameter is less than zero or greater than or equal to the size property return early
step 2: if the index parameter is equal to zero, the return the shift shift method.
step 3: if the index is equal to the size property minus
1 return the pop method.
step 4: Create a variable prevNode and set it to the results of get method with index-1.
step 5: Get the node at the index -1 position,
step 6: Create a temp variable and set it equal to the prevNode's next property, create another afterNode and set it to be the temp's variable next property, then set the prevNode's next property to be the afterNode, set the afterNode prev's property to be the prevNode, set hte temp's next and temp's prev property to null
step 7: decrement the size property by 1 and return the list

Javascript의 코드 구현:

   remove(index){
       if(index<0 || index >= this.size ) return undefined
       if(index === 0) return this.shift()
       if(index === this.size-1) return this.pop()
        let prevNode = this.get(index-1)
        let temp = prevNode.next
        let afterNode = temp.next
        prevNode.next = afterNode
        afterNode.prev = prevNode
        temp.next = null
        temp.prev = null
        this.size--
        return this

   }

python에서 다음을 수행합니다.

def remove(self,index):
         if index<0 or index>= self.size: return
         if index == 0:
             return self.shift()
         if index == self.size-1:
            return self.pop()
         prevNode = self.get(index-1)
         temp = prevNode.next
         afterNode = temp.next
         prevNode.next = afterNode
         afterNode.prev = prevNode
         temp.next = None
         temp.prev = None
         self.size-=1
         return self

JavaScript의 최종 코드 솔루션:

class Node{
    constructor(val){
        this.val= val
        this.prev = null
        this.next=null

    }
}

class DLL{
    constructor(){
        this.head= null
        this.tail= null
        this.size= 0

    }

    push(val){
        let newNode= new Node(val);
        if(!this.head){
            this.head=newNode
            this.tail= newNode
            this.size++
            return this
        }
        this.tail.next = newNode
        newNode.prev =this.tail
        this.tail = newNode
        this.size++
        return this
    }
    pop(){
        if(!this.head) return undefined;
        let temp = this.tail
        if(this.size ===1){
            this.head = null;
            this.tail = null;
        }else{
        this.tail=this.tail.prev;
        this.tail.next = null;
        temp.prev= null;
        }
        this.size--;

        return this;
    }

   //shift
   shift(){
       if(!this.head) return undefined
       let temp = this.head;
       if(this.size ===1){
           this.head = null
           this.tail =null;
       }else{
       this.head = this.head.next;
       this.head.prev = null
       }
       this.size --;

       return temp
   }
   //unshift
   unshift(val){
       let newNode = new Node(val);
       if(!this.head){
           this.head= newNode;
           this.tail = newNode;
       }else{
           newNode.next = this.head;
           this.head.prev = newNode;
           this.head = newNode;
       }
       this.size++;
       return this;


   }
   //get
   get(index){
       if(index<0 || index >= this.size)return undefined;
       let current;
       if(index >Math.floor(this.size/2)){
           let count=this.size-1;
            current= this.tail;
          while(count !== index){
             current= current.prev;
             count--
       }

       }else{
           let count=0;
            current= this.head;
           while(count !== index){
              current= current.next;
              count++
       }
       }
       return current;
   }
   //set
   set(index, val){
        let node = this.get(index);
        if(node){
            node.val = val;
            return true;
        }
        return false;
   }
   //insert
   insert(index, val){
       if(index<0 || index > this.size ) return undefined
       if(index === 0){
           this.unshift(val);
       }else if(index === this.size){
           this.push(val);
       }else{
           let newNode = new Node(val);
           let node  = this.get(index -1);
           let nextNode = node.next;
               node.next = newNode, newNode.prev = node;
               newNode.next = nextNode, nextNode.prev = newNode
       }

      this.size++;
      return this;

   }
   //remove
   remove(index){
       if(index<0 || index >= this.size ) return undefined
       if(index === 0) return this.shift()
       if(index === this.size-1) return this.pop()
        let prevNode = this.get(index-1)
        let temp = prevNode.next
        let afterNode = temp.next
        prevNode.next = afterNode
        afterNode.prev = prevNode
        temp.next = null
        temp.prev = null

        this.size--
        return temp

   }
   //reverse

   //print
   print(){
       let current= this.head
       let arr = []
       while(current){
           arr.push(current.val)
           current = current.next
       }
       return arr
   }
}
let list =new DLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)

Python의 경우:

import math
class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None


class DLL:
    def __init__(self):
        self.head=None
        self.tail= None
        self.size=0

    def traverse_list(self):
        if(self.head is None):

            print("No elements in this list")
            return
        else:
            n = self.head
            while n is not None:
                print(n.val)
                n = n.next


    def push(self,val):
        newNode =  Node(val)

        if(self.head == None):
            self.head = newNode
            self.tail = newNode
            self.size+=1
            return self
        self.tail.next= newNode
        newNode.prev = self.tail
        self.tail = newNode
        self.size+=1
        return self

    def pop(self):

        if self.head ==None:return
        temp = self.tail
        if self.size == 1:
            self.head = None
            self.tail = None
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None 
        self.size-=1

        return self

    def shift(self):
            if self.head == None: return 
            temp = self.head
            if(self.size == 1):
                self.head = None
                self.tail = None
            else:
                self.head = self.head.next
                self.head.prev = None
            self.size-=1

            return temp

    def unshift(self,val):
        newNode = Node(val)
        if self.head == None:
            self.head = newNode
            self.tail = newNode
        else:
            newNode.next = self.head
            self.head.prev = newNode
            self.head = newNode
        self.size+=1
        return self

    def get(self,index):
        if index <0 or index >=self.size:return
        if index > math.floor(self.size/2):      
            current= self.tail
            count = self.size -1
            while count != index:       
                current = current.next
                count-=1
        else:
            current= self.head
            count = 0
            while count != index:   
                current = current.next
                count+=1
        return current

    def set(self,index,val):
        node = self.get(index)
        if node :
            node.val = val
            return True
        return False

    def insert(self,index, val):
        if index<0 or index> self.size: return
        if index == 0: return self.unshift(val)
        if index == self.size: return self.push(val)
        newNode = Node(val)
        prevNode = self.get(index-1)
        nextNode = prevNode.next
        prevNode.next = newNode 
        newNode.prev= prevNode
        newNode.next = nextNode 
        nextNode.prev = newNode
        self.size+=1
        return self

    def remove(self,index):
         if index<0 or index>= self.size: return
         if index == 0:
             return self.shift()
         if index == self.size-1:
            return self.pop()
         prevNode = self.get(index-1)
         temp = prevNode.next
         afterNode = temp.next
         prevNode.next = afterNode
         afterNode.prev = prevNode
         temp.next = None
         temp.prev = None
         self.size-=1
         return self

list = DLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
list.traverse_list()   

print("==============")
list.remove(2)
print("==============")
print("==============")
list.traverse_list()   

print("==============")

보시다시피 최종 해결 방안은 SLL 해결 방안과 비슷한 점이 있지만 약간의 차이도 있다.

DLL의 이점:

더블 링크 목록을 반전시키는 것은 매우 쉽다.

실행 시 메모리를 쉽게 할당하거나 재할당할 수 있습니다.

는 단일 체인 테이블과 마찬가지로 가장 실현하기 쉬운 데이터 구조이다.

이 쌍사슬표의 범람은 양방향인데 이것은 단사슬표에서 불가능하다.

단일 체인 테이블에 비해 노드를 삭제하는 것이 쉽다.단일 체인 테이블은 삭제할 노드와 이전 노드를 가리키는 바늘을 삭제해야 하지만, 이중 체인 테이블에서는 삭제할 바늘만 필요합니다.

DLL의 단점:

는 수조와 단일 체인 테이블에 비해 추가 메모리를 사용한다.

메모리의 요소는 무작위로 저장되기 때문에 순서대로 요소에 접근할 수 없으며 직접 접근할 수 없습니다.

결론

쌍사슬표와 그 용도에 대한 더 많은 정보는 이것article을 보십시오.이 시리즈의 다음 글은 체인 테이블을 사용하여 창고와 대기열을 실현하는 방법을 소개할 것이다.