[자료구조] Data Structure - 자바 Linked List

강의가 두 개로 나뉘어있는데, 나눈 이유는 ArrayList와 LinkedList의 장단점이 확연이 다르기 때문이라고 한다.

상황에 따라 알맞은 것을 사용하여 효율을 극대화할 수 있으므로, 장단점에 대하여 확실히 알아두면 좋을 것 같다.

 

 

출처 : https://opentutorials.org/module/1335/8857

우선 Linked List를 생성하게되면 엘리먼트 (노드) 하나당 메모리를 각각 차지하여, 분산되어있는 형태를 띄우게 된다.

그리고 영어이름 그대로, 연결 리스트이므로, 노드 객체 하나당, Data filed와 그것을 연결해주는 Link filed가 필요하다.

 

Linked List의 장점은, Array List와 달리, 엘리먼트의 추가 / 삭제를 할 시 이전 , 이후의 참조값만 변경하면 됨으로써, 속도가 빠르다. 

 

특정 index값을 이용하여 배열의 찾는데에 있어서는 Array List가 강하고, 요소의 추가 / 삭제가 자주 일어날 경우 Linked List가 더 효율적임을 알 수 있다.

 

- trade off

트레이드 오프란, 어떠한 특성이 좋아지면 다른 특성이 나빠지는 상황을 의미한다고 한다.

Array List와 Linked List는 트레이드 오프의 좋은 사례라고 할 수 있다고 한다.

우리가 자료구조를 배우는 이유 중 하나는 이러한 트레이드오프를 이해하기 위해서이다.

장점과 단점의 균형을 이해할 수 있어야 올바른 선택을 할 수 있기 때문이다.

 

아래의 그림은 이해를 돕기위하여 생활코딩 사이트의 이미지를 인용하였다.

출처 : https://www.opentutorials.org/module/1335/8821

큰 내용들은 아래의 강의에서 참조하면 이해가 훨씬 수월하다. 위에 참조로 사용한 그림도 안에 포함되어있으며, 더욱더 이해하기 쉽게끔 그림 및 설명이 정말 잘되어있다.

 

www.opentutorials.org/module/1335/8821

Linked list - Data Structure (자료구조)

강의에도 나왔듯이, JCF Linked List와는 달리 단방향 연결 리스트로 되어 있으며 Java Collections framework의 Linked List 양방향으로써 앞뒤 위치를 모두 알 수 있게끔 코딩되어 있다. 소스 자체에도 여러 문제가 존재할 수 있다.

하나 공부하는 데에 있어 도움이 많이 되었으며 처음 접하시는 분이면 참조하여 공부가 되었으면 좋겠다.

 

 

 

이번 것도 마찬가지로, Java로 기능 구현해보며 좀 더 수월하게 이해가 되었다.

Source 코드도 마찬가지로, 따로 코딩하여 git으로 올려두었다.

 

git address : github.com/egjeon/data-structure-linked-list