One Paper: Linked List

* 필요한 문장으로 판단되는 경우에 발췌했으며, 출처 표기를 준수하였습니다.

* 본 글은 개인 노션에서 만들어 티스토리에서 재구성했습니다. (노션 접속은 본 줄의 문장을 클릭)

Linked List(링크드 리스트)

링크드 리스트는 IPL(Information Processing Language)를 주로 다룬 RAND 회사의 Allen Newll, Cliff Shaw and Herbert A. Simon에 의해 발달되었다.

 

링크드리스트는 lists, stacks, queues, associative arrays, S-expressions 같은 데이터 구조에 흔히 사용되며, 종류로 Singly Linked List, Doubly Linked List, Circular Linked List, Doubly Circular Linked List, Grounded Headed Linked List가 있다.

 

컴퓨터 사이언스에서, 링크드리스트는 메모리 안에서 물리적인 배치에 의해 순서가 주어진 데이터 요소들의 선형적인 모음들(집합체)이다. (말이 너무 어렵다) 각각의 요소들은 다음 요소를 가리킨다. 그 이유는 데이터 구조에서 노드는 최소한의 단위로 존재한다. 이 노드들은 데이터를 담고 있으며 다른 노드들을 가리킨다. 그리고 이 노드들은 포인터에 의해 움직인다.

 

노드0: 12와 포인터 / 노드1: 99와 포인터 / 노드2: 37과 포인터 / 노드3: null

• 전 문장에서 다른 문장을 가리킨다는 의미를 알아보자.
  노드라는 집에는 정보가 담긴 데이터와 레퍼런스(다른 말로, 링크)로 이루어져 있는데, 여기서 레퍼런스(다른 말로, 링크)라는 것이 다음 노드로 가야 된다고 알려주고 있는 것이다. 게임에서 이 퀘스트를 완수하면 다른 퀘스트가 기다리듯이 말이다.
• 위 문장에서 레퍼런스라는 용어는 컴퓨터 사이언스에서는 변숫값이나 메모리 값과 같이 간접적으로 특정한 테이터에 접근할 수 있는 물리적인 주소 값을 의미한다.

이런 구조는 어떤 동작이 반복되는 동안 임의의 위치가 어떻든 요소들의 효율적인 삽입과 제거가 가능하게 한다. 하지만, 링크드 리스트는 선형적으로(첫 번째부터 마지막까지) 하나하나 다 탐색해야 해야 한다는 문제점이 있다. 그렇기 때문에 마음대로 원하는 값에 접근하는 것은 실현할 수 없다.

 

링크드 리스트의 주된 장점은 흔히 배열과 비교가 된다. 링크드 리스트는 구조를 재할달, 재조직할 필요 없이 삽입과 제거가 가능하다. 왜냐하면 데이터 항목들은 메모리나 디스크에 저장될 필요가 없기 때문이다. 링크드리스트는 리스트 탐색이 가능하기 때문에 어떤 리스트의 노트이든 삽입과 제거가 가능하다. 그러기 때문에 리스트의 길이 도한 증가 및 감소가 필요에 따라 유동적으로 변할 수 있다. 각각의 노드들은 반드시 이전의 노드들을 가리킬 필요까지는 없기에.

단점으로,

1. 배열보다 메모리를 더 잡아먹는다. 포인터들이 가리키는 주소 값을 저장하고 있기 때문이다.
2. 반드시 리스트의 시작부터 순서대로 탐색해야 된다.
3. 노드가 메모리나 디스크에 저장될 필요가 없기에, 노드는 리스트에 있는 개별 요소들에 접근하기 위한 시간 소모가 증가된다. (특히, CPU 캐시)
4. 반대 탐색, 마지막 노드에서 처음 노드까지 반대로 탐색이 어렵다.(singly-list)
   예외로, doubly linked lists는 다소 다루기 쉽다.

동작 원리: Singly Linked list operations(some fuctions)

1. 삽입(Insertion Code Snippet)

function insertBefore(Node node, newVal)
    if node = null    // assume list is empty
        newNode := new Node(data:=newVal, next:=newNode)
    else
        newNode := new Node(data:=node.data, next:=node.next)
        node.data := newVal
        node.next := newNode
    update firstNode variable if necessary

node := list.firstNode
while node not null
    (do something with node.data)
    node := node.next

2. 제거(Remove Code Snippet)

function remove(Node node)
    if node ≠ null and size of list > 1
        removedData := node.data
        node.data := node.next.data
        node.next = node.next.next
        return removedData

 

• 동작 원리에 대해 더 알고 싶으시다면, 다음 링크를 확인해보세요.

Linked List Operations: Traverse, Insert and Delete

Linked Lists in JavaScript (ES6 code)

 

 

 

 

 

 

실생활에서의 링크드 리스트: Applications of linked list in real world 

1. Image viewer – Previous and next images are linked, hence can be accessed by next and previous button.
2. Previous and next page in web browser – We can access previous and next url searched in web browser by pressing back and next button since, they are linked as linked list.
3. Music Player – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list.

 

---

 

참고 자료:
Node: https://en.wikipedia.org/wiki/Node_(computer_science)

Linked LIst: https://en.wikipedia.org/wiki/Linked_list#:~:text=In computer science%2C a linked,which together represent a sequence.

reference: https://en.wikipedia.org/wiki/Reference_(computer_science)

RAND: https://en.wikipedia.org/wiki/RAND_Corporation

types: https://www.geeksforgeeks.org/types-of-linked-list/

Applications of linked list in real world: https://www.geeksforgeeks.org/applications-of-linked-list-data-structure/

operation: https://codeburst.io/linked-lists-in-javascript-es6-code-part-1-6dd349c3dcc3