Linked List Data Structure(링크드 리스트 자료구조)

1. 링크드 리스트(Linked List) 란?

배열의 단점을 해결하고자 만든 자료구조로 몇개의 배열을 선언할 지 알 수 없기 때문에 이를 해결하기 위한 자료구조이다.
고리와 고리를 연결한 형태로 각각의 데이터가 다음 데이터가 누구인지 알고 있는 데이터 구조이다.

 

장점:

• 추가와 삭제가 용이하다.
• 미리 사이즈를 할당할 필요가 없다.

단점:

• 탐색 속도가 느리다.

 

링크드 리스트는 두가지 형태로 존재할 수 있다.

Head-to-Tail search structure
헤드부터 테일까지 노드의 연결로 구조화 되어있다.
더미노드
헤드와 테일을 지정하지 않고 노드를 중심으로 연결된 자료구조 형태

 

***마지막 노드(테일)는 항상 null을 가리킨다.

 

노드(or vertex): 각 객체, 자료
데이터필드(data field) : 데이터의 값이 저장된 공간
링크필드(link field) : 데이터의 값이 연결된 다음 노드의 정보를 가진 공간
헤드(Head) : 링크 리스트의 시작 노드
테일(Tail) : 링크 리스트의 마지막 노드로 연결된 노드가 존재하지 않는 노드

 

 

2. 링크드 리스트의 활용

• 웹 브라우저 방문기록
• 페이지 뒤로가기와 앞으로가기

 

3. 구현을 위한 의사코드(Pseudo Code)

1. 데이터와 다음 데이터의 값을 가진 노드를 생성한다.
    1-1. 새 노드 생성시 다음값으로 null로 가리킨다.
    1-2. 링크드 리스트 생성시 자료의 수와 헤드를 포함한 객체를 생성한다. 때 헤드는 null을 가리킨다.
2. 링크드 리스트에 맞는 메소드함수를 구현한다.
    2-1. append(data) : 새로운 데이터 추가시 두가지 경우를 가진다.
        2-1-1. 만약 헤드가 null을 가리키면, 헤드가 새로 생성된 데이터를 가리키게 한다.
        2-1-2. 만약 헤드가 다음 데이터를 가르키고 있으면 그 다음 데이터가 새로운 데이터를 가리키게 하고 데이터를 추가한다.
        2-1-3. 자료의 수에 1을 더한다.
    2-2. removeAt(location) : 데이터의 위치에 따라 데이터를 삭제한다.
        2-2-1. 삭제하고자 하는 데이터의 이전 데이터가 삭제하고자 하는 데이터의 다음 데이터를 가리키게 하고 삭제할 데이터는 null을 가리키게 한다.
        2-2-2. 만약 리스트의 첫번째를 삭제하려면 헤드를 다음 데이터로 바꾸고 삭제할 데이터는 null을 가리키게 한다.
        2-2-3. 자료의 수에 1을 뺀다.
    2-3. indexOf(data) : 데이터를 순서대로 따라가면서 인덱스를 더해준다. 일치하는 데이터를 찾으면 인덱스를 반환한다.
    2-4. remove(data) : 데이터 값을 기준으로 삭제를 원할 때 인덱스의 값을 찾아 일치하는 값을 removeAt(index)로 삭제한다.
    2-5. insert(location, data) : 원하는 위치에 데이터를 추가할 때 인덱스 값을 기준으로 위치를 찾고 데이터를 추가한다.
    2-6. isEmpty() : 자료의 수가 0 이상이면 true를 반환한다.
    2-7. length() : 리스트내 전체 자료의 수를 반환한다.

 

 

4. 참고자료(References)

https://otrodevym.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%A7%81%ED%81%AC%EB%93%9C-%EB%A6%AC%EC%8A%A4%ED%8A%B8Linked-List
https://www.zerocho.com/category/Algorithm/post/58008a628475ed00152d6c4d
https://m.blog.naver.com/PostView.nhn?blogId=pgh7092&logNo=221093740186&proxyReferer=https%3A%2F%2Fwww.google.com%2F
https://opentutorials.org/module/1335/8821
https://boycoding.tistory.com/33