JavaScript와 Python의 단일 체인 테이블 구현

무엇이 체인 시계입니까?

codementor에 따르면 체인 테이블은 무한량의 항목을 저장할 수 있는 데이터 구조이다.이러한 항목은 포인터를 사용하여 순서대로 연결됩니다.체인 테이블의 원소를 노드라고 부른다.노드에는 데이터와 다음 두 개의 필드가 있다.데이터 필드는 특정 노드에 저장된 데이터를 포함합니다.그것은 단지 하나의 변수일 수 없다.노드의 데이터 부분을 나타내는 변수가 많을 수 있습니다.다음 필드는 다음 노드의 주소를 포함합니다.이것이 바로 노드 간에 링크를 구축하는 곳이다.링크 목록을 참조하려면 abbrev SLL을 사용합니다.

나의 정의는 매우 간단하다. 이것은 데이터 구조로 노드로 구성되고 노드는 데이터를 저장하는value 속성을 가지며 다음 속성은 다음 노드를 가리킨다.이렇게 하면 한 노드는 그 다음 노드만 알고 체인의 다른 노드는 모른다.

우리가 실행할 행동

//를 눌러 노드 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 - then reset the tail to point to the newNode and increment the size

JavaScript의 코드 구현:

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

    }
}

class SLL{
    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
        this.tail = newNode
        this.size++
        return this
    }
}

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

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

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


class SLL:
    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
        self.tail = newNode
        self.size+=1
        return self
list = SLL()
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 current and newTail variable, set the current variable to the head node then set the newTail to the current variable
step 3 - traverse the list while current.next exists and setting newTail equal to the current node after each iteration.
The loop will break at the n-1 node if we assume the size of the nodes is n
step 4 - Set the tail attribute equal to the new tail. the tail .next equal to null and decrement the size of the list by 1.
step 5 - check if the size is zero, if so set the head and tail equal to None or null then return the removed node or list

Javascript의 코드 구현:

pop(){
        if(!this.head) return undefined;
        let current= this.head;
        let newTail=current;
        while(current.next){
            newTail = current;
            current= current.next;
        }
        this.tail= newTail;
        this.tail.next= null;
        this.size--;
        if(this.size ===0){
            this.head = null;
            this.tail = null;
        }
        return this
    }

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

def pop(self):
        if self.head ==None:return
        current = self.head
        new_tail = None
        while current.next is not None:
            new_tail = current
            current = current.next

        self.tail = new_tail
        self.tail.next = None
        self.size-=1
        if self.size == 0:
            self.head = None
            self.tail = None
        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: set the head property to be the current heads next property
step 4: decrement the size by 1
step 5: Edge case check if the size is down to zero if it is set the tail to null and return the list

Javascript의 코드 구현:

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

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

def shift(self):
        if self.head == None: return 
        temp = self.head
        self.head = self.head.next
        self.size-=1
        if(self.size == 0):
            self.tail = None
        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 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 = 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 = 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 Create variable count set to zero , create variable current set it equal to the head property
step 3: count is not equal to index set current=current.next and increment count by 1
step 4: when the loop breaks return current

Javascript의 코드 구현:

  get(index){
       if(index<0 || index >= this.size)return undefined;
       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
        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, the 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 val passed in.
step 5: Get the node at the index -1 position
step 6: Create a temp 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 newNodes's next property to temp.
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 temp = node.next;
               node.next = newNode;
               newNode.next = temp;
       }

      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)
        temp = prevNode.next
        prevNode.next = newNode
        newNode.next = temp
        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
step 7: set the prevNode's next property to the temp's variable next property
step 8: 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
        prevNode.next = temp.next
        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
         prevNode.next = temp.next
         self.size-=1
         return self

역전

이 메서드는 목록의 방향을 반대로 바꿉니다.시작은 끝이고, 끝은 새로운 시작이다.기본적으로 우리는 처음부터 시작할 것이다. 처음부터 시작할 것이다.다음은 따라야 할 절차를 개술하였다

step 1 : Create a node variable and set it equal to head property
step 2: Set the head property to the tail property and the tail property to the node variable
step 3: Create a Next and prev variable and set them both to null or None.
step 4: Start a loop for when it is within the size property's range take 1 step from zero.
step 5: In each step set the Next variable to the current node's next property, set the current node's next property to the prev variable, set the prev variable to the current node and finally set the node variable to the Next variable.
step 6: Return the list

주의: 최종 해결 방안을 검사하면 print라는 추가 방법이 있습니다. 이 방법은 값을 순서대로 수조에 넣고 수조로 되돌려줍니다. 반방향 방법을 테스트하기 위해서입니다. 그렇지 않으면 필요없습니다.목록을 처음 인쇄할 때, 입력한 순서에 따라 목록을 되돌려주고, 목록을 반전시켜 다시 인쇄해야 합니다.작업이 성공했음을 표시하기 위해 되돌아오는 그룹은 상반되어야 합니다.
Javascript의 코드 구현:

 reverse(){
       let node = this.head;
       this.head= this.tail;     // 20 -> 21 -> 22 -> 23
       this.tail = node;     // reversed           21 -> 20 -> null
       let Next,
           prev=null;
       for(let i =0;i< this.size;i++){
           Next= node.next
           node.next=prev
           prev = node
           node = Next        
       }
       return this

   }

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

def reverse(self):
        node = self.head
        self.head = self.tail
        self.tail = node
        prev = Next =None
        for i in range(self.size):
            Next = node.next
            node.next = prev
            prev = node
            node = Next
            i+=1
        return self

JavaScript의 최종 코드 솔루션:

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

    }
}

class SLL{
    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
        this.tail = newNode
        this.size++
        return this
    }
    pop(){
        if(!this.head) return undefined;
        let current= this.head;
        let newTail=current;
        while(current.next){
            newTail = current;
            current= current.next;
        }
        this.tail= newTail;
        this.tail.next= null;
        this.size--;
        if(this.size ===0){
            this.head = null;
            this.tail = null;
        }
        return this;
    }

   //shift
   shift(){
       if(!this.head) return undefined
       let temp = this.head;
       this.head = this.head.next;
       this.size --;
       if(this.size ===0){
           this.tail =null;
       }
       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 = newNode;
       }
       this.size++;
       return this;


   }
   //get
   get(index){
       if(index<0 || index >= this.size)return undefined;
       let count=0;
       let 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 temp = node.next;
               node.next = newNode;
               newNode.next = temp;
       }

      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
        prevNode.next = temp.next
        this.size--
        return this

   }
   //reverse
   reverse(){
       let node = this.head;
       this.head= this.tail;     // 20 -> 21 -> 22 -> 23
       this.tail = node;     // reversed           21 -> 20 -> null
       let Next,
           prev=null;
       for(let i =0;i< this.size;i++){
           Next= node.next
           node.next=prev
           prev = node
           node = Next        
       }
       return this

   }

   //print
   print(){
       let current= this.head
       let arr = []
       while(current){
           arr.push(current.val)
           current = current.next
       }
       return arr
   }
}

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

Python의 경우:

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


class SLL:
    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
        else:
            self.tail.next= newNode
            self.tail = newNode      
        self.size+=1
        return self

    def pop(self):
        if self.head ==None:return
        current = self.head
        new_tail = None
        while current.next is not None:
            new_tail = current
            current = current.next

        self.tail = new_tail
        self.tail.next = None
        self.size-=1
        if self.size == 0:
            self.head = None
            self.tail = None
        return self


    def shift(self):
        if self.head == None: return 
        temp = self.head
        self.head = self.head.next
        self.size-=1
        if(self.size == 0):
            self.tail = None
        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 = newNode
        self.size+=1
        return self



    def get(self,index):
        if index <0 or index >=self.size:return
        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)
        temp = prevNode.next
        prevNode.next = newNode
        newNode.next = temp
        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
         prevNode.next = temp.next
         self.size-=1
         return self



    def print(self):
        arr=[]
        current= self.head
        while current:
            arr.append(current.val)
            current= current.next
        return arr


    def reverse(self):
        node = self.head
        self.head = self.tail
        self.tail = node
        prev = Next =None
        for i in range(self.size):
            Next = node.next
            node.next = prev
            prev = node
            node = Next
            i+=1
        return self


list = SLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
print("|||||||||||||")

list.traverse_list
print("***************")
print(list.print())
print("===============")
list.reverse()
print("===============")
print(list.print())

체인 테이블의 이점:

동적 데이터 구조: 체인 테이블은 동적 배열이기 때문에 메모리를 분배하고 방출하여 운행할 때 증가하고 수축할 수 있다.따라서 체인 시계의 초기 크기를 제시할 필요가 없다.

메모리 낭비가 없다. 체인 테이블에서 효율적인 메모리 이용률을 실현할 수 있다. 체인 테이블의 크기가 운행할 때 증가하거나 감소하기 때문에 메모리 낭비가 없고 메모리를 미리 분배할 필요가 없다.

실현: 창고와 대기열 등 선형 데이터 구조는 보통 체인 테이블로 쉽게 실현할 수 있다.
삽입과 삭제 작업: 체인 테이블에 삽입과 삭제 작업이 비교적 쉽다.요소를 삽입하거나 삭제한 후에는 요소를 이동하지 않고 다음 포인터의 주소만 업데이트하면 됩니다.

체인 테이블의 단점:

메모리 사용: 수조에 비해 체인 테이블은 더 많은 메모리를 필요로 한다.체인 테이블에는 다음 요소의 주소를 저장하기 위한 바늘이 필요하고, 그 자체에 추가 메모리가 필요하기 때문이다.

스트리밍: 체인 테이블에서 스트리밍은 수조보다 시간이 더 걸린다.체인 테이블에서 색인에 따라 배열된 그룹처럼 요소에 직접 접근할 수 없습니다.예를 들어 위치 n에 접근하기 위해서는 그 전의 모든 노드를 훑어보아야 한다.

역방향 범람: 단일 체인 테이블에서 역방향 범람은 불가능하지만 쌍체인 테이블에서 역방향 범람은 가능하다. 왜냐하면 각 노드를 가리키기 전에 연결된 노드의 지침을 포함하기 때문이다.이 동작을 실행하기 위해서는 뒷바늘에 추가 메모리가 필요하기 때문에 메모리를 낭비할 수 있습니다.

랜덤 접근: 체인 테이블의 동적 메모리 분배로 인해 체인 테이블에 랜덤 접근이 불가능하다.

결론

체인 테이블의 실현은 언어와 무관하다. 그 배후의 논리를 이해하면, 당신이 선택한 어떤 언어로도 그것을 실현할 수 있다.위 단계를 따르기만 하면 됩니다.