컴퓨터의 자료를 저장하는 구조의 한 종류이다.
일렬로 연결된 데이터를 저장할 떄 사용한다.
데이터를 저장할 수 있는 공간이 있으면 그 안에 다음 데이터의 주소를 가지고 있는 구조이다.
LinkedList를 이야기할 때 배열이랑 비교를 안할 수 없다.
배열은 방들이 물리적으로 한 곳에 모여있다. 그래서 한번 크기를 정하면 늘리거나 줄일 수 없다.
그에 반해 LinkedList는 데이터를 중간에 삽입하고자 하면 앞에 있는 노드가 가지고 있던 노드를 자기가 갖고 앞에 있는 노드에게는 너 다음 나야 알려주면 된다. 반대로 데이터를 삭제하고자 한다면 해당 노드가 가지고 있던 다음 노드의 주소를 앞에 노드에게 주면 된다.
노드가 삭제 됐지만 메모리를 차지하고 있기 때문에 자바에서는 안쓰이는 변수를 알아서 처리해주지만(gc),
C, C++에서는 반드시 안쓰겠다고 명시를 해줘야 한다.
LinkedList는 주소를 하나하나 찾아다녀야 되서 배열보다 속도가 느릴 수 있다. 하지만, 삽입하고 삭제하는 것을 배열로 구현을 하게 된다면 배열을 통째로 다시 선언해서 복사하고 하나 추가하고 해야하기 때문에 길이가 정해지지 않는 데이터를 핸들링 할 때는 LinkedList가 좋을 것 같다.
LinkedList 단반향
LinkedList 양방향
다음 주소를 가지고 있고 추가로 내 앞에 있는 주소를 추가로 가지고 있다.
앞뒤로 자유롭게 다닐 수 있다.
데이터를 삽입할 때는 삽입하고자 하는 전 노드가 가지고 있던 다음 주소를 내가 갖는다. 다음 노드로는 내 주소를 준다. 내 주소를 받은 노드는 가지고 있던 전 주소를 나한테 넘기면 된다.
데이터를 삭제할 때는 삭제하고자 하는 노드의 다음 주소를 전 노드로 넘기고 전 주소를 내 다음 노드로 넘기면 된다.