Linked List(링크드 리스트)

Linked List 란?

 

링크드 리스트는 "노드" 들의 조합으로 이루어진 선형적인 배열이다.

A linked list is a collection of "nodes" that together from a linear ordering.

 

각자의 노드들은 포인터를 지니고있고 이 포인터들은 다음 노드를 가르킨다.

또한 노드들은 각자 지정된 "값" 들이있다.

Each node stores a pointer, called next, to the next node of the list. In addition, each node stores its associated element.

 

 

 

이는 무슨말일까?

 

예를들어 환자의 정보가 담긴 링크드 리스트를 작성한다고 해보자.

그렇다면 하나의 노드는

 

class Node

{

  Node* nextPtr;

  string name;

  string patientNumber;

  string disease;

  .

  .

  .

}

 

이런식의 구조를 갖게 될 것이다.

 

 

보통 링크드 리스트는 이전 노드를 가르키는 포인터를 지니고 있지 않은데 이를

 

Singly Linked List 라고 부른다.

Singly Linked List

 

 

 

이에 반대로 이전 노드의 포인터를 지니고 있는 구조체를 

 

Double Linked List 라고 부른다.

Double Linked List