2020.08.10 수정 & 복습
자바를 하고 계시던 분이라면
Linked List 를 처럼 들었을땐 , 그냥 흔하게 자주 쓰는거라 ..쉽게 이해하실것 같다.
Linked list (연결 리스트) 는 각 노드 가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로
데이터를 저장하는 자료 구조입니다.
-
노드(node): 데이터를 담고 있는 그릇. 주로 class로 구현되기 때문에 class라고 생각해도 상관 없습니다.
-
링크(link): 리스트의 순서를 유지할 수 있게 해주는 연결고리.
쉽게 말하면 데이터를 저장할수 있는 공간이 있으면 그 공간안에 다음 데이터의 주소를 가지고 있는 구조입니다.
이게 배열과 차이점이 무엇이냐면 배열은 물리적인 공간이 한공간에 정해져있습니다.
Linked List 는 중간에 다른 주소값을 바라보면 연결을 할수 있습니다 .
Doubly Linked List
Linked List 는 다음 노드 뿐만이 아니라 전 노드의 링크도 가지고 있는 연결 리스트 입니다.
사실 당연하게 이전 리스트 연결이 되서 index 불러와져야하는것이 아닌가 ?? 생각이 들수 있다.
저도 Linked List 가 약간 참조와 역참조 처럼 주소를 바라보고있다면
바라보고있는 주소와 거기에 역 주소에 대한 index 도 당연히 불러와져야하는것이 아닌가 ?? 라는 생각이 들었다 .
Circular Linked List
꼬리 (tail) 부분이 머리 (head) 부분과 연결이 되어 있는 연결 리스트 입니다.
리스트의 무한 반복이 가능합니다.
Array와 차이점
Array와 마찬가지로 순차열적으로 요소들을 저장한다는 점에서는 비슷하나 근본적으로 많은 차이를 가지고 있습니다.
-
배열(array)는 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적입니다. 연결리스트도 데이터를 논리적 순서에 따라 데이터를 입력하지만 물리적 주소는 순차적이지 않습니다.
-
배열은 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 때문에 데이터 접근 속도가 매우 빠릅니다 (indexing). 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하고 있습니다. 그럼으로 한번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능함으로 배열에 비해 원하는 데이터에 접근 하는 속도가 떨어집니다.
-
배열은 데이터의 삽입/삭제에는 취약합니다. 배열 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문입니다. 연결리스트에서 데이터 삽입/삭제는 논리적 주소만 바꿔주면 되기 때문에 훨씬 쉽습니다.
-
동일한 양의 데이터를 저장해도 일반적으로 연결 리스트가 배열보다 더 많은 메모리를 차지하게 됩니다 (배열은 단순 데이터 저장인데 비해 연결 리스트는 각 노드마다 객체를 생성해야 함으로).
how to use
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class LinkedList:
def __init__(self):
self.headval = None
list1 = LinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3