[data structure] 자료구조 링크리스트, 연결리스트(Linked List) 알고리즘 이란?? (java 로 구현)

Q. 연결리스트 (Linked List) 에 대해 알아보자.

1. 연결리스트(Linked List) ??

2. 연결리스트와 함께 하는 대표적인 기능들(add, delete, insert, search, clear, print)

1. 연결리스트(Linked List) ??

연결리스트란 배열과 같은 순차(Sequential) 표현에서 제기된,

문제점인 데이터 이동을 보완 위한 방법입니다.

그럼 이전에 문제였던 순차리스트 표현에서 제기된 문제점을 알아보겠습니다.

아래와 같이 꽉찬 배열이 있다고 가정했을때,

[2], [3], [5] 번의 데이터가 삭제 됐을때,

그 뒤에 있는 데이터를 앞으로 가져와야 하는 배열간의 복사가 일어나게 됩니다.

위와 같은 그림처럼 값 50, 70, 80이 삭제된 빈 배열때문에 앞으로 이동되게 됩니다.

(일반적으로 데이터 저장시 빈공간은 두지 않기 때문)

이전 배열은 추가(add) 하는데에는 아무런 문제가 없지만,

삽입(insert), 삭제(delete) 하는데는 배열 복사, 이동 등 많은 소요가 필요했었습니다.

바로 이를 잘 해결하도록 나온것이 연결 리스트(Linked List) 입니다.

연결 리스트는 아래와 같은 모습을 가지게 됩니다.

사각형을 노드(Node)라고 부르는데,

노드는 data 부분과 address(link) 부분으로 불립니다.

data 부분은 값을, address 부분은 다음 데이터의 위치를 기억하고 있습니다.

노드들을 여러개 붙여 놓으면 아래와 같은 모습을 가지게 됩니다.

[그림] 연결리스트(Linked List) : 위키백과

http://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

각 노드들이 자기 다음 데이터의 위치를 기억하고 있기 때문에,

화살표로 연결되어 있는 모습을 볼수 있습니다.

private static class Node { private Object data; Node next; }

자기 다음 데이터의 위치를 기억하고 있기 때문에,

삽입(insert)과 삭제(delete)가 용이해집니다.

삽입 삭제가 용이해지는 이유는,

위 그림과 같이 가운데 노드가 없어진다면,

①노드에서 ②노드를 향하고 있는 주소값을 지우고,

①노드에서 ③노드를 향하게하면 됩니다.

이렇게 구현하면 삽입이나, 삭제시 발생하는 배열 복사를 줄일수 있습니다.

각 노드는 자기 다음 데이터의 위치를 기억하고 있지만,

어디가 시작이 되는지는 알수가 없습니다.

그렇게 때문에 first 라는 시작점을 가르키는 객체가 필요 합니다.

끝이란 표현은 address 부분에 null 을 사용하여,

이 데이터가 끝이란 것을 알립니다.

데이터의 추가, 삽입과 삭제는 용이 하지만,

연결리스트는 시작점 밖에 알고 있는것이 없기 때문에,

데이터를 찾기 위해선 처음부터 끝까지 비교해야한다는 단점이 있습니다.

2. 연결리스트와 함께 하는 대표적인 기능들(add, delete, insert, search, clear)

연결리스트(Linked List) 에는,

연결리스트 마지막에 데이터를 추가하는 add

연결리스트 중간에 데이터를 삽입하는 insert

연결리스트의 값을 삭제하는 delete

연결리스트의 값을 찾는 search

연결리스트를 초기화 시키는 clear

이렇게 대표적인 기능(메소드)이 필요 합니다.

가장 먼저 add 는 아래와 같이 구성됩니다.

private Node first; public void add( Object data ) { Node node = first; // ① if( node == null ) // ② { node = new Node(); node.data = data; first = node; } else { for( ;; ) { if( node.next == null ) // ③ { Node newNode = new Node(); newNode.data = data; node.next = newNode; break; } node = node.next; } } }

① : 첫번째 노드를 node 에 넣습니다.

② : 첫번째 노드가 있는지 확인하고 없다면(null), 새 노드를 생성합니다.

③ : ②번의 그 외의 경우에는,

루프를 돌아 가장 마지막 노드를 찾습니다. (노드의 다음 값(node.next)이 null)을 찾습니다.

※ node.next 가 null 이면 가장 마지막 노드란 뜻입니다.

두번째로 delete 는 아래와 같이 구성됩니다.

public void delete( Object data ) { Node node = first; if( node.data.equals( data ) ) // ① first = node.next; else { for( ;; ) { Node nextNode = node.next; if( nextNode.data.equals( data ) ) // ② { node.next = nextNode.next; break; } else   {     if( nextNode.next == null ) // ③       return; node = nextNode;   } } } }

① : 최초 노드 값을 삭제해야 한다면, 첫번째 노드를 바꿔치기 합니다.

② : ①번이 아니라면, 루프를 돌아 해당 값을 찾습니다.

node(기준 값), nextNode(다음 값)이 있는데,

다음 값을 찾아서 값과 같다면 기준 값에 주소부분에 nextNode.next 값을 넣어줍니다.

③ : 끝까지 루프를 돌아도 찾지 못하였을 경우 메소드를 종료합니다.

세번째로 insert 는 다음과 같습니다.

public void insert( Object baseData, Object insertData ) { Node node = first; if( ( node.data ).equals( baseData ) ) // ① { Node newNode = new Node(); newNode.data = insertData; newNode.next = first; first = newNode; } else { for( ;; ) { Node nextNode = node.next; if( nextNode.data.equals( baseData ) ) // ② { Node newNode = new Node(); newNode.data = insertData; newNode.next = nextNode; node.next = newNode; break; } else node = nextNode; } } }

insert 는 기준값 앞에 값을 넣는 메소드 입니다.

① : 첫번째 노드의 값이 기준값과 같다면 새 노드를 추가하여 first 노드로 바꿔치기 해줍니다.

② : ①번의 경우가 아니라면, 루프를 돌아 기준값을 찾고 새 노드를 기준값 앞에 추가해줍니다.

네번째로 search 는 다음과 같습니다.

public void search( Object data ) { Node node = first; int cnt = 1; for( ;; ) { if( node.data.equals( data ) ) // ① { System.out.println( "'" + data + "' is " + cnt + " node" ); break; } if( node.next == null ) // ② return; else node = node.next; cnt++; } }

① : 처음부터 루프를 돌아 해당값을 찾고 그에 맞는 index 를 출력합니다.

② : 맨끝까지 돌아도 없을 경우에는, 메소드를 종료 시킵니다.

마지막으로 clear 입니다.

public void clear() { System.out.print( "\n\n    - clear -" ); first = new Node(); }

시작점인 first 노드를 새로 생성하여 초기화 합니다.

C 책을 보고 작성하려 했을 때, 기본 개념과 뭔가 많이 헷갈렸습니다.

자바는 OOP(Object-Oriented Programming) 는 연결리스트를 보다 쉽게 구성할수 있었습니다.

많이 천천히 생각해보고, 자바와 더 친해져봐야겠습니다.

참조 : 위키백과

http://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

참조 : C로 쓴 자료 구조론 2nd Edition 155 155 page ~ 171 page