list (linked list, double linked list)

테이프를 쓸때는 랜덤 엑세스 불가능

메모레: 랜덤 엑세스 가능

 

---

 

선형 배열 (linear array), 연결리스트(linked list) 모두 데이터 원소들을 순서를 지어 늘어놓는다.

 

처이점 = 선형 배열은 번호가 붙여진 칸에 원소들을 채워넣는 방식/ 연결 리스트는 각 원소들을 줄줄이 엮어서 관리하는 방식

-  array list에서는 엘리먼트라는 이름을 사용

- linked list와 같이 연결된 엘리먼트들은 노드(node, 마디, 교점의 의미) 혹은 버텍스(vertex, 정점, 꼭지점의 의미)라고 부른다.

연결성이 강조된 표현!

 

---

 linked list 구조

 

 

보통 데이터 필드는 value라는 이름의 변수, 링크 필드는 next 변수를 사용

value에는 노드의 값이 저장되고, next에는 다음 노드의 포인터나 참조값을 저장해서 노드와 노드를 연결시킨다.

---

-> 연결리스트의 장점 =

연결 리스트에서는 원소들이 링크 (link) 라고 부르는 고리로 연결되어 있으므로,

가운데에서 끊어 하나를 삭제하거나, 아니면 가운데를 끊고 그 자리에 다른 원소를 (원소들을) 삽입하는 것이 선형 배열의 경우보다 쉽다.(빠른 시간 내에 처리할 수 있다.)

이러한 이점 때문에, 원소의 삽입/삭제가 빈번히 일어나는 응용에서는 연결 리스트가 많이 이용된다.

컴퓨터 시스템을 구성하는 중요한 요소인 운영체제 (operating system) 의 내부에서도 이러한 연결 리스트가 여러 곳에서 이용되고 있다..

 

단점 = 

1) 선형 배열에 비해서 데이터 구조 표현에 소요되는 저장 공간 (메모리) 소요가 크다.

링크 또한 메모리에 저장되어 있어야 하므로, 연결 리스트를 표현하기 위해서는 동일한 데이터 원소들을 담기 위하여 사용하는 메모리 요구량이 더 크다.

 2) k 번째의 원소 를 찾아가는 데에는 선형 배열의 경우보다 시간이 오래 걸린다.

선형 배열에서는 데이터 원소들이 번호가 붙여진 칸들에 들어 있으므로 그 번호를 이용하여 대번에 특정 번째의 원소를 찾아갈 수 있지만

연결 리스트에서는 단지 원소들이 고리로 연결된 모습을 하고 있으므로 특정 번째의 원소를 접근하려면 앞에서부터 하나씩 링크를 따라가면서 찾아가야 한다.

 

---

양방향 연결 리스트 (Doubly Linke lists)

=  노드들이 앞/뒤로 연결되어 있다. 즉, 인접한 두 개의 노드들은 앞의 노드로부터 뒤의 노드가 연결되어 있을뿐만 아니라, 뒤의 노드로부터 앞의 노드도 연결되어 있다. 한 노드의 입장에서 보자면, 자신보다 앞에 오는 노드를 연결하는 링크와 자신보다 뒤에 오는 노드를 연결하는 링크를 둘 다 가진다.

장점 =

1) 양방향 연결 리스트가 단방향 연결 리스트에 비해서 가지는 장점: 데이터 원소들을 차례로 방문할 때, 앞에서부터 뒤로도 할 수 있지만 뒤에서부터 앞으로도 할 수 있다.

실제로 운영체제 (operating system) 등에서는 리스트를 대상으로 앞/뒤로 왔다 갔다 하면서 작업을 행하는 일들이 빈번히 요구되고, 따라서 양방향 연결 리스트가 많이 이용되고 있다.

 

단점 = 

1) 링크를 나타내기 위한 메모리 사용량이 늘어난다.

2)원소를 삽입/삭제하는 연산에 있어서 앞/뒤의 링크를 모두 조정해야한다.(귀찮..)

 

 

https://opentutorials.org/module/1335/8821

Linked list - Data Structure (자료구조)