꿈 많은 사람의 이야기

지난 글에서 파이썬으로 연결리스트를 구성해봤습니다.(https://lsjsj92.tistory.com/461) 하지만 단순한 연결리스트는 단방향만 가기 때문에 양방향보다는 효율이 떨어집니다 그것을 보완하기 위해 양방향으로 갈 수 있는 연결 리스트를 구상했는데요 그게 이중 연결 리스트(doubly linked list) 입니다. 그림으로 보면 아래와 같은 구조입니다. 각 노드가 있고 노드안에 prev, next가 있어서 prev는 본인 노드 전의 지점을 가리킵니다. next는 본인 노드 다음의 노드를 가리킵니다. 어렵지 않는 구조이죠 지난 번 포스팅에서 크게 달라지는 것은 없으며 prev 구조가 추가 되었습니다. 이게 끝입니다 ㅎㅎ 단순하죠? 하지만 삽입이나 삭제 같은 연산을 할 때는 좀 많이 달라집니다...

연결리스트란 자료가 링크로 연결되어 있는 구조를 말한다. 말 다 필요없고 그림으로 보면 간단하다. 이렇게 되어 있는 것이 연결리스트이다. 예시로 설명하면 노드는 이름과, 다음번지 값을 가지고 있다. 10번지 노드는 이름이 김, 다음번지(20)의 값 20번지 노드는 이름이 이, 다음번지(30)의 값 30번지 노드는 이름이 박, 다음번지(40)의 값 40번지 노드는 이름이 홍, 다음번지(null)의 값 이다. 40번지 값이 가장 최근에 들어온 값으로 했다 (새로운 노드를 start 지점에 두는 방법도 있지만 본인은 이런식으로 구현했다) 기본적으로 자바에선 LinkedList를 클래스로 제공해주지만 직접 소스로 구현해보면 객체지향, 자료구조 등의 측면에서 많은 도움이 된다. cur은 값이 추가될 때마다 맨 끝..