Linked List는 아마 알고리즘을 구현하기 위한 가장 기본적 자료구조가 아닐까 싶다. Linked List는 어떤 데이터에 다음 데이터를 가르키는 포인터를 두고 데이터를 계속 연결해서 추가하는 자료 구조체이다. 배열에 비해서 메모리를 절약할수 있는 장점이 있으나, 특정 데이터에 접근하기 위해서는 그 데이터를 찾는 과정이 필요하다. 다음은 Linked List의 종류이다.
Linked List구현은 어렵지 않다. 데이터와 포인터로 구성된 노드를 생성하고 포인터가 다음에 추가되는 데이터를 가르키게 하면 된다. 다음은 Single Linked List와 그 연산들을 자바로 간단하게 구현한 코드이다.
public class LinkedList {
private class Node { Object mNodeData; Node mNextNode; public Node(Object inData){ mNodeData=inData; } }
private Node mRootNode=null; private Node mLastNode=null; public LinkedList(){ } public void insertLast(Object inData){ Node newNode=new Node(inData); newNode.mNextNode=null; if(mRootNode==null) { mRootNode=newNode; mLastNode=mRootNode; } else { mLastNode.mNextNode=newNode; mLastNode=newNode; } } public void insertAt(Object inData,int inAt){ Node newNode=new Node(inData); newNode.mNextNode=null; if(mRootNode==null) { mRootNode=newNode; mLastNode=mRootNode; } else { Node pivotNode=mRootNode; Node prevNode=null; while(pivotNode!=null && inAt-->0){ prevNode=pivotNode; pivotNode=pivotNode.mNextNode; } if(prevNode==null) { newNode.mNextNode=mRootNode; mRootNode=newNode; } else { prevNode.mNextNode=newNode; newNode.mNextNode=pivotNode; } } } public int getNodeCount(){ Node pivotNode=mRootNode; int retCnt=0; while(pivotNode!=null){ pivotNode=pivotNode.mNextNode; retCnt++; } return retCnt; } public Object getNode(int inAt){ Node pivotNode=mRootNode; while(pivotNode!=null && inAt-->0){ pivotNode=pivotNode.mNextNode; } if(pivotNode==null) return null; else return pivotNode.mNodeData; } public Object deleteNode(int inAt){ Node pivotNode=mRootNode; Node prevNode=null; while(pivotNode!=null && inAt-->0){ prevNode=pivotNode; pivotNode=pivotNode.mNextNode; } if(pivotNode==null) return null; else { prevNode.mNextNode=pivotNode.mNextNode; return pivotNode.mNodeData; } } public void printList(){ Node pivotNode=mRootNode; while(pivotNode!=null){ System.out.print(pivotNode.mNodeData+" "); pivotNode=pivotNode.mNextNode; } System.out.println("");; }
public static void main(String[] args){ LinkedList linkedList=new LinkedList(); linkedList.insertLast(new Integer(1)); linkedList.insertLast(new Integer(2)); linkedList.insertLast(new Integer(3)); linkedList.printList(); linkedList.deleteNode(1); linkedList.printList(); linkedList.insertAt(new Integer(2), 1); linkedList.printList(); linkedList.insertAt(new Integer(2), 5); linkedList.printList(); linkedList.insertAt(new Integer(2), 4); linkedList.printList(); linkedList.insertAt(new Integer(2), 0); linkedList.printList(); System.out.println(linkedList.getNodeCount()); } } |
