<div id="readability-page-1" class="page"><div>
                                            <p><a href="/m/category/Data%20structure%2C%20Algorithm/Data%20structure%20in%20js">Data structure, Algorithm/Data structure in js</a></p><h2>자료구조 in javascript (2): Linked list. 배열과는 다르다!</h2>
                    <p><cite>
                        <span>DarrenKwonDev</span>
                    </cite>
                </p></div><p><time>2021. 5. 26. 16:49</time>
                    <span>
                        
                                                    <a href="#comment" onclick="Utils.smoothScroll(this);return false">
                                
                            </a>
                        
                                                    <span id="title_daumlike">
                                
                                <span id="mobile-reaction"></span>
                                
                            </span>
                                            </span>
                </p><div>
                    <h4 data-ke-size="size20"><b>배열과 리스트는 다르다!</b></h4>
<p data-ke-size="size16">포인터 개념이 있는 Go에서는 이 지점이 명확하게 보이는데, javascript에서는 포인터가 없으니 애매하게 보인다.</p>
<p data-ke-size="size16">애매하다기보다 "이걸 왜 구현해야지? js에선 배열 쓰면 되는데?"라는 생각.</p>
<p data-ke-size="size16">어쨌거나 개념적인 설명과 구현체에 대해서는 아래 Go를 기반으로 한 포스트가 오히려 더 잘 이해된다.</p>

<p data-ke-size="size16"><a href="https://darrengwon.tistory.com/1403?category=919438">https://darrengwon.tistory.com/1403?category=919438</a>&nbsp;</p>
<figure id="og_1622007450714" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="article" data-og-title="리스트(List)의 이해 및 배열(Array)과의 비교" data-og-description="https://golang.org/pkg/container/list/ 리스트는 각 데이터를 담고 있는 요소를 포인터로 연결한 자료구조이다. 포인터로 연결되었다는 점을 강조하기 위해 Linked List라고 부르기도 한다. 포인터로 연결되" data-og-host="darrengwon.tistory.com" data-og-source-url="https://darrengwon.tistory.com/1403?category=919438" data-og-url="https://darrengwon.tistory.com/1403" data-og-image="https://scrap.kakaocdn.net/dn/bhOAsA/hyKllE84po/sS6hJflTdkYkF7jc1DJQCk/img.png?width=800&amp;height=212&amp;face=0_0_800_212,https://scrap.kakaocdn.net/dn/bFZhuE/hyKli9vBL2/DvRPdcl8xMPU4uX95MSwn1/img.png?width=800&amp;height=212&amp;face=0_0_800_212,https://scrap.kakaocdn.net/dn/HKkrt/hyKlkGgMkh/AoYkNySW0NkmcghlwEJWo0/img.png?width=1372&amp;height=569&amp;face=0_0_1372_569"><a href="https://darrengwon.tistory.com/1403?category=919438" target="_blank" rel="noopener" data-source-url="https://darrengwon.tistory.com/1403?category=919438">

<div>
<p data-ke-size="size16">리스트(List)의 이해 및 배열(Array)과의 비교</p>
<p data-ke-size="size16">https://golang.org/pkg/container/list/ 리스트는 각 데이터를 담고 있는 요소를 포인터로 연결한 자료구조이다. 포인터로 연결되었다는 점을 강조하기 위해 Linked List라고 부르기도 한다. 포인터로 연결되</p>
<p data-ke-size="size16">darrengwon.tistory.com</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/bhOAsA/hyKllE84po/sS6hJflTdkYkF7jc1DJQCk/img.png?width=800&amp;height=212&amp;face=0_0_800_212,https://scrap.kakaocdn.net/dn/bFZhuE/hyKli9vBL2/DvRPdcl8xMPU4uX95MSwn1/img.png?width=800&amp;height=212&amp;face=0_0_800_212,https://scrap.kakaocdn.net/dn/HKkrt/hyKlkGgMkh/AoYkNySW0NkmcghlwEJWo0/img.png?width=1372&amp;height=569&amp;face=0_0_1372_569"></figure>

<p data-ke-size="size16">하나의 <u><b>node</b></u>에는 <u><b>data</b></u>과 <u><b>address</b></u>가 있다고 이해하자.&nbsp;</p>
<p data-ke-size="size16">여튼 연결 리스트를 (굳이 굳이) javascript로 list를 구현해보도록하자.</p>
<figure data-origin-width="1280" data-origin-height="340" data-ke-mobilestyle="widthOrigin"><span data-url="https://blog.kakaocdn.net/dn/AqARb/btq5OSiztsC/RDDlAM13YAZVnCa1xHuvIk/img.png" data-lightbox="lightbox" data-alt=""><img src="https://blog.kakaocdn.net/dn/AqARb/btq5OSiztsC/RDDlAM13YAZVnCa1xHuvIk/img.png" data-origin-width="1280" data-origin-height="340" data-ke-mobilestyle="widthOrigin"></span></figure>


<h4 data-ke-size="size20"><b>리스트 구현 ADT(abstract data type)</b></h4>

<p data-ke-size="size16">우선 어느 정도로 구현할지에 대한 수준이 필요합니다. List는 보통 아래와 같은 스펙을 가지고 있어야 합니다.</p>
<p data-ke-size="size16">메서드 이름까지 같진 않더라도, 어떤 기능을 구현해야 하는지에 대한 스펙을 얻을 수 있습니다.</p>
<pre id="code_1622010330965" data-ke-language="javascript" data-ke-type="codeblock"><code>get() – Return an element from the list at any given position. 
insert() – Insert an element at any position of the list.
remove() – Remove the first occurrence of any element from a non-empty list.
removeAt() – Remove the element at a specified location from a non-empty list.
replace() – Replace an element at any position by another element.
size() – Return the number of elements in the list.
isEmpty() – Return true if the list is empty, otherwise return false.
isFull() – Return true if the list is full, otherwise return false.

출처 - https://www.geeksforgeeks.org/abstract-data-types/#:~:text=ADT%2C%20Queue%20ADT.-,List%20ADT,the%20data%20in%20the%20list.</code></pre>

<p data-ke-size="size16">여기서는 모든 list의 ADT를 구현하지는 않고, 적당한 수준에서만 구현하도록 하겠습니다.&nbsp;</p>
<p data-ke-size="size16">(실제로 쓸 것도 아닌데 ㅜㅜ)</p>

<h4 data-ke-size="size20"><b>LinkedList와 Node 구현&nbsp; : 시도 1</b></h4>
<p data-ke-size="size16">LinkedList는 head(첫 node)를 가지고</p>
<p data-ke-size="size16">ListNode는 data와 다음 Node를 가리키는 next를 가지고 있습니다. prev까지 구현하면 이중 연결 리스트가 되겠죠.</p>
<p data-ke-size="size16">추가로, 인자로 받은 node들이 Node의 instanceof인지 체크하여 안정성을 높이는 방법이 있겠으나 여기서는 생략하겠습니다.</p>

<pre id="code_1622014001069" data-ke-language="javascript" data-ke-type="codeblock"><code>class LinkedList {
  constructor(head = null) {
    this.head = head;
    this.length = 0;
  }

  append(node) {
    if (!this.head) {
      this.head = node;
    } else {
      this.end().next = node;
    }
    this.length++;
  }

  find(index) {
    let current = this.head;
    let count = 0;
    while (count &lt; index) {
      current = current.next;
      count++;
    }
    return current; // node 반환
  }

  clear() {
    this.head = null;
  }

  end() {
    let lastNode = this.head;
    while (lastNode.next) {
      lastNode = this.head.next;
    }
    return lastNode;
  }

  front() {
    return this.head;
  }
  
  ... 이하 생략
}

class ListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

let node1 = new ListNode(1);

// linked list 인스턴스 생성
let list = new LinkedList();

// node 추가
list.append(node1);

// index로 node 찾기
console.log(list.find(2));

</code></pre>


<h4 data-ke-size="size20"><b>LinkedList와 Node 구현&nbsp; : 시도 2</b></h4>
<p data-ke-size="size16">제가 보는 책에서 구현되어 있는 것을 class로 제가 손을 좀 본 코드입니다.</p>
<p data-ke-size="size16">개인적으로, 배열을 내부적으로 써서 linked list를 구현했던데 이러면 구현하는 의미가 퇴색된다고 생각합니다.</p>
<p data-ke-size="size16">그래도 편하니까 올려봅니다.</p>

<pre id="code_1622014601671" data-ke-language="javascript" data-ke-type="codeblock"><code>class LinkedList {
  constructor() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = [];
  }

  // node간 움직임을 담당하는 front, end, prev, next
  // 그리고 index(pos)에 따라 node를 출력하는 getElement

  front() {
    this.post = 0;
  }

  end() {
    this.pos = this.listSize - 1;
  }

  prev() {
    if (this.pos &gt; 0) this.pos--;
  }

  next() {
    if (this.pos &lt; this.listSize - 1) {
      this.pos++;
    }
  }

  curPos() {
    return this.pos;
  }

  moveTo(pos) {
    this.pos = pos;
  }

  getElement() {
    return this.dataStore[this.pos];
  }

  // 그 외 여러 utils

  clear() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = [];
  }

  length() {
    return this.listSize;
  }

  find(element) {
    for (let i = 0; i &lt; this.dataStore.length; ++i) {
      if (this.dataStore[i] == element) {
        return i;
      }
    }
    return -1;
  }

  toString() {
    return this.dataStore;
  }

  append(element) {
    this.dataStore[this.listSize++] = element;
  }

  remove(element) {
    let foundAt = this.find(element);
    if (foundAt &gt; -1) {
      this.dataStore.splice(foundAt, 1);
      --this.listSize;
      return true;
    }
    return false;
  }

  insert(element, after) {
    let insertPos = this.find(after);
    if (insertPos &gt; -1) {
      this.dataStore.splice(insertPos + 1, 0, element);
      this.listSize++;
      return true;
    }
    return false;
  }
}

let names = new LinkedList();

names.append('Cynthia');
names.append('Raymond');
names.append('Barbara');
names.append('Darren');

console.log(names.length(), names.toString());

names.remove('Raymond');
console.log('after remove Raymond', names.toString());

names.insert('Martin', 'Barbara');
console.log('add Martin after Barbara', names.toString());

console.log('get first element', names.getElement()); // 첫 원소

names.moveTo(2);
names.prev();

console.log(names.getElement());

names.clear();
</code></pre>


<p data-ke-size="size16">ref)</p>
<p data-ke-size="size16"><a href="https://velog.io/@760kry/JS-Linked-List-vs-Array-List-data-structor" target="_blank" rel="noopener">https://velog.io/@760kry/JS-Linked-List-vs-Array-List-data-structor</a></p>
<p data-ke-size="size16"><a href="https://www.zerocho.com/category/Algorithm/post/58008a628475ed00152d6c4d" target="_blank" rel="noopener">https://www.zerocho.com/category/Algorithm/post/58008a628475ed00152d6c4d</a></p>
<p data-ke-size="size16"><a href="https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/" target="_blank" rel="noopener">https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/</a></p>


                                                            
                    
					
                    
                    
                </div></div>

HotHandCoding

DarrenKwon

배열과 리스트는 다르다!
포인터 개념이 있는 Go에서는 이 지점이 명확하게 보이는데, javascript에서는 포인터가 없으니 애매하게 보인다.
애매하다기보다 "이걸 왜 구현해야지? js에선 배열 쓰면 되는데?"라는 생각.
어쨌거나 개념적인 설명과 구현체에 대해서는 아래 Go를 기반으로 한 포스트가 오히려 더 잘 이해된다.
 
https://darrengwon.tistory.com/1403?category=919438 
 
하나의 node에는 data과 address가 있다고 이해하자. 
여튼 연결 리스트를 (굳이 굳이) javascript로 list를 구현해보도록하자.
 
 
리스트 구현 ADT(abstract data type)
 
우선 어느 정도로 구현할지에 대한 수준이 필요합니다. List는 보통 아래와 같은 스펙을 가지고 있어야 합니다.
메서드 이름까지 같진 않더라도, 어떤 기능을 구현해야 하는지에 대한 스펙을 얻을 수 있습니다.
get() – Return an element from the list at any given position. 
insert() – Insert an element at any position of the list.
remove() – Remove the first occurrence of any element from a non-empty list.
removeAt() – Remove the element at a specified location from a non-empty list.
replace() – Replace an element at any position by another element.
size() – Return the number of elements in the list.
isEmpty() – Return true if the list is empty, otherwise return false.
isFull() – Return true if the list is full, otherwise return false.
출처 - https://www.geeksforgeeks.org/abstract-data-types/#:~:text=ADT%2C%20Queue%20ADT.-,List%20ADT,the%20data%20in%20the%20list.
 
여기서는 모든 list의 ADT를 구현하지는 않고, 적당한 수준에서만 구현하도록 하겠습니다. 
(실제로 쓸 것도 아닌데 ㅜㅜ)
 
LinkedList와 Node 구현  : 시도 1
LinkedList는 head(첫 node)를 가지고
ListNode는 data와 다음 Node를 가리키는 next를 가지고 있습니다. prev까지 구현하면 이중 연결 리스트가 되겠죠.
추가로, 인자로 받은 node들이 Node의 instanceof인지 체크하여 안정성을 높이는 방법이 있겠으나 여기서는 생략하겠습니다.
 
class LinkedList {
  constructor(head = null) {
    this.head = head;
    this.length = 0;
  }
  append(node) {
    if (!this.head) {
      this.head = node;
    } else {
      this.end().next = node;
    }
    this.length++;
  }
  find(index) {
    let current = this.head;
    let count = 0;
    while (count < index) {
      current = current.next;
      count++;
    }
    return current; // node 반환
  }
  clear() {
    this.head = null;
  }
  end() {
    let lastNode = this.head;
    while (lastNode.next) {
      lastNode = this.head.next;
    }
    return lastNode;
  }
  front() {
    return this.head;
  }
  
  ... 이하 생략
}
class ListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
let node1 = new ListNode(1);
// linked list 인스턴스 생성
let list = new LinkedList();
// node 추가
list.append(node1);
// index로 node 찾기
console.log(list.find(2));
 
 
LinkedList와 Node 구현  : 시도 2
제가 보는 책에서 구현되어 있는 것을 class로 제가 손을 좀 본 코드입니다.
개인적으로, 배열을 내부적으로 써서 linked list를 구현했던데 이러면 구현하는 의미가 퇴색된다고 생각합니다.
그래도 편하니까 올려봅니다.
 
class LinkedList {
  constructor() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = [];
  }
  // node간 움직임을 담당하는 front, end, prev, next
  // 그리고 index(pos)에 따라 node를 출력하는 getElement
  front() {
    this.post = 0;
  }
  end() {
    this.pos = this.listSize - 1;
  }
  prev() {
    if (this.pos > 0) this.pos--;
  }
  next() {
    if (this.pos < this.listSize - 1) {
      this.pos++;
    }
  }
  curPos() {
    return this.pos;
  }
  moveTo(pos) {
    this.pos = pos;
  }
  getElement() {
    return this.dataStore[this.pos];
  }
  // 그 외 여러 utils
  clear() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = [];
  }
  length() {
    return this.listSize;
  }
  find(element) {
    for (let i = 0; i < this.dataStore.length; ++i) {
      if (this.dataStore[i] == element) {
        return i;
      }
    }
    return -1;
  }
  toString() {
    return this.dataStore;
  }
  append(element) {
    this.dataStore[this.listSize++] = element;
  }
  remove(element) {
    let foundAt = this.find(element);
    if (foundAt > -1) {
      this.dataStore.splice(foundAt, 1);
      --this.listSize;
      return true;
    }
    return false;
  }
  insert(element, after) {
    let insertPos = this.find(after);
    if (insertPos > -1) {
      this.dataStore.splice(insertPos + 1, 0, element);
      this.listSize++;
      return true;
    }
    return false;
  }
}
let names = new LinkedList();
names.append('Cynthia');
names.append('Raymond');
names.append('Barbara');
names.append('Darren');
console.log(names.length(), names.toString());
names.remove('Raymond');
console.log('after remove Raymond', names.toString());
names.insert('Martin', 'Barbara');
console.log('add Martin after Barbara', names.toString());
console.log('get first element', names.getElement()); // 첫 원소
names.moveTo(2);
names.prev();
console.log(names.getElement());
names.clear();
 
 
ref)
https://velog.io/@760kry/JS-Linked-List-vs-Array-List-data-structor
https://www.zerocho.com/category/Algorithm/post/58008a628475ed00152d6c4d
https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/

자료구조 in javascript (2): Linked list. 배열과는 다르다!

댓글