JavaScript를 사용한 기본 데이터 구조 - 연결 목록 - 1부🚀

목차
* 🤓 INTRODUCTION
* ❔ ABOUT LINKED LISTS
* 1️⃣ SINGLY-LINKED LIST
* 👨🏻‍🔬 OPERATIONS
* 🖖🏻 PSEUDOCODES
* 🙏 THANK YOU

🤓 소개

Welcome, my dear code-dudes and code-dudettes!🚀 Welcome to yet another blog article about elementary data structures.

If you missed the previous article you can check it out here:

Today, we are going to discuss a new data structure called Linked Lists. Because the topic of the linked list has many operations that we need to explain and understand through simple English words and pseudocode, this is going to be a two-part article so that you can enjoy it and not find it overwhelming.

Also, please feel free to connect with me via , or



❔ 연결된 목록 정보

A linked list is a data structure in which the objects are arranged in a linear order. But, online an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets.

The size of the list is the number of elements in the list.
A list can be a sorted list or an unsorted list.

연결된 목록 유형


  • 단일 연결 목록
  • 이중 연결 목록
  • 순환 목록
  • 비원형 목록
  • 제목이
  • 인 목록
  • 제목이 없는 목록
  • 정렬된 목록
  • 정렬되지 않은 목록

  • 1️⃣ 단일 연결 목록

    This type of a linked list is a data structure that contains a sequence of nodes. Each node has two fields: info and link.

    An info field - remembers an element of a list or an address of an element of a list
    A link field - remembers an address of the next node in the list

    👨🏻‍🔬 운영

    • Traversal
    • Finding an element in the list
    • Adding a node to the list
    • Deleting a node from the list
    • Deleting the list
    • Copying the list
    • Concatenating the list

    🖖🏻 유사 코드

    The pseudocode of the many operations that we will learn is a good starting point.

    순회



    이 알고리즘은 모든 요소의 목록을 통과합니다.
    "PROCESSING"작업을 적용합니다.
    포인터 POINT는 항상 다음에 처리될 노드를 가리킵니다.

    
    1 POINT => START //POINT - the first element in the list
    2 while(POINT is not NULL)
    3    PROCESS(info(node)) //do what ever you want with the info
    4    POINT => link(POINT) //set point the the next element stored 
    5                          //in the link field
    6 endwhile
    7 exit
    


    정렬되지 않은 목록 검색



    이 알고리즘은 정렬되지 않은 연결 목록에서 요소 E를 검색하고 발견된 요소의 위치를 ​​반환합니다.
    LOC = 검색에 실패한 경우 NULL(위치는 NULL)

    1 POK => START
    2 while (POK is not NULL AND info(POK) is not someValue)
    3    POK => link(POK) //go to the next element in the list
    4 endwhile
    5 if info(POK) is equal to someValue
    6 then
    7    LOC => POK //Success
    8 else
    9    LOC => NULL //Element not found
    10 exit procedure
    


    정렬된 목록 검색



    이 알고리즘은 정렬된 연결 목록에서 요소 E를 검색하고 찾은 요소의 위치를 ​​반환합니다.
    LOC = 검색에 실패한 경우 NULL(위치는 NULL)

    1 POK => START
    2 while(POK is not NULL)
    3    if (info(POK) is equal to someValue)
    4       LOC => POK
    5       exit procedure //element found
    6    else if (someValue is less than info(POK)) then
    7       LOC => NULL
    8       exit procedure //element not found
    9    else
    10      POK => link(POK) //go to the next element
    11   endif
    12 endwhile
    13 LOC => NULL
    14 exit procedure
    


    목록 시작 부분에 삽입



    이 알고리즘은 연결된 목록의 시작 부분에 요소 E를 삽입합니다.

    1 new => getNode()  //Get a new empty node
    2 info(new) = E  //write element into our newly created node
    3 link(new) => START  //connect a new node
    4 START => new
    5 exit procedure
    


    목록의 특정 위치에 삽입



    이 알고리즘은 노드 LOC 뒤에 요소 E를 삽입합니다. LOC가 null이면 E가 목록의 첫 번째 요소로 삽입됩니다.

    1 new => getNode() //get a new empty node
    2 info(new) => E  //populate our new node
    3 if(LOC=null) then
    4    link(new) => START
    5    START => new  //E is inserted as a new Node
    6 else
    7    link(new) => link(LOC)
    8    link(LOC) => new   //E is inserted after the node LOC
    9 exit procedure
    


    정렬된 목록에 삽입



    이 알고리즘은 정렬된 연결 목록에 요소 E를 삽입합니다.

    1 call findA(start, E, loc) //find the location of the node that 
    2                          //precedes node E
    3 call insertAfterLoc(start, E, loc) //insert E after node loc
    4 exit procedure
    


    정렬된 목록 메서드 "findA"에 삽입



    이 알고리즘은 정렬된 목록에서 info(LOC)가 E보다 작은 마지막 노드의 위치 LOC를 찾거나 검색에 실패하면 LOC가 null임을 반환합니다.

    1 if (START is null) then
    2   LOC => null
    3   return      //Empty list
    4 if (E < info(START)) then
    5   LOC => null
    6   return   //borderline case
    7 spoint => START //start pointer
    8 npoint => link(START) //next pointer
    9 while (point is not NULL)
    10   if (E less than info(npoint)) then
    11      LOC => spoint
    12      return
    13   spoint => npoint
    14   npoint => link(npoint)   //updating indexes
    15 endwhile
    16 LOC => spoint
    17 return
    


    목록 처음부터 삭제



    이 알고리즘은 연결된 목록의 시작 부분에서 요소 E를 삭제합니다.

    1 point => START //set the pointer to the beginning of the list
    2 START => link(point) //change the beginning of the list
    3 E => info(point)  // read the value of an element E
    4 freenode(point)   //free the node
    5 exit procedure    //end of an algorithm
    


    꽤 많죠? 😲 예, 그렇기 때문에 실제 JavaScript 코드 구현을 계속하기 전에 이러한 의사 코드를 앉아서 분석하는 것이 좋습니다. 단계별로 진행하고 모든 의사 코드가 수행하는 작업을 이해해 보세요. 이것은 단지 추상화일 뿐이라는 것을 기억하세요. 하지만 이 기사의 다음 부분에서 진지한 JavaScript 코딩에 들어갈 것입니다.

    🙏 읽어주셔서 감사합니다!

    References:
    School notes...
    School books...

    Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!

    ☕ SUPPORT ME AND KEEP ME FOCUSED!


    즐거운 해킹 시간 되세요! 😊

    좋은 웹페이지 즐겨찾기