链表的实现一个是 node,一个是 List。node 是链表每个基本组成部分,List 操作 node。我的思路大概是这样。
node 部分代码:
- class Node{
- private Object data;
- private Node next;
- public Node(Object data){
- this.data = data;
- }
- public void setNext(Node next){
- this.next = next;
- }
- public void setData(Object data){
- this.data = data;
- }
- public Object getData(){
- return this.data;
- }
- public Node getNext(){
- return this.next;
- }
- }
List 实现一系列对链表的操作:
- class List{
- private Node root;
- private Node point;
- private int count;
- public void add(Node node){
- if(root == null){
- this.root = node;
- this.point = node;
- }else{
- this.point.setNext(node);
- this.point = node;
- }
- this.count ++;
- }
- public int size(){
- return this.count;
- }
- public boolean isEmpty(){
- return this.root == null ? true : false;
- }
- public boolean contain(Object data){
- return isContain(this.root,data);
- }
- public Object getData(int index){
- if(index<0||index>=this.count){
- return null;
- }
- return getDataByIndex(this.root,0,index);
- }
- public void setData(Object data,int index){
- if(index<0||index>=this.count){
- return;
- }
- setDataByIndex(this.root,0,index,data);
- }
- public void deleteData(Object data){
- if(this.contain(data)){
- deleteNodeByData(this.root,data);
- }
- return;
- }
- public void deleteNode(int index){
- if(index<0||index>=this.count){
- return;
- }
- deleteNodeByIndex(this.root,0,index);
- }
- public Object[] toArray(){
- Object[] array = new Object[this.count];
- toArrayBy(this.root,array,0);
- return array;
- }
- public void clear(){
- this.root = null;
- this.count = 0;
- System.gc();
- }
- public void deleteNodeByData(Node node,Object data){
- if(data.equals(this.root.getData())){
- this.root = this.root.getNext();
- this.count--;
- return;
- }
- if(data.equals(node.getNext().getData())){
- node.setNext(node.getNext().getNext());
- this.count--;
- return;
- }
- deleteNodeByData(node.getNext(),data);
- }
- private void toArrayBy(Node node,Object[] array,int point){
- if(node == null){
- return;
- }
- array[point] = node.getData();
- toArrayBy(node.getNext(),array,++point);
- }
- private void deleteNodeByIndex(Node node,int point,int index){
- if(index == 0){
- this.root = this.root.getNext();
- this.count--;
- return;
- }
- if(point == index-1){
- node.setNext(node.getNext().getNext());
- this.count--;
- return;
- }
- deleteNodeByIndex(node.getNext(),++point,index);
- }
- private void setDataByIndex(Node node,int point,int index,Object data){
- if(point == index){
- node.setData(data);
- return;
- }
- setDataByIndex(node.getNext(),++point,index,data);
- }
- private Object getDataByIndex(Node node,int point,int index){
- System.out.println("point="+point);
- System.out.println("index="+index);
- if(point == index){
- return node.getData();
- }
- return getDataByIndex(node.getNext(),++point,index); // ++ can not use behind point
- }
- private boolean isContain(Node node,Object data){
- if(node == null){
- return false;
- }
- if(data.equals(node.getData())){
- return true;
- }
- return isContain(node.getNext(),data);
- }
- private void print(Node node){
- if(node == null){
- return;
- }
- System.out.println(node.getData());
- print(node.getNext());
- }
- public void printAll(){
- print(this.root);
- }
- }
测试代码:
- public class TestDemo{
- public static void main(String[] args){
- List list = new List();
- System.out.println(list.isEmpty());
- System.out.println(list.size());
- list.add(new Node("first"));
- list.add(new Node("second"));
- list.add(new Node("third"));
- Object[] array = list.toArray();
- for(int i = 0;i<array.length;i++){
- System.out.println(i+"="+array[i]);
- }
- System.out.println(list.size());
- System.out.println(list.isEmpty());
- list.printAll();
- System.out.println("isContain first:"+list.contain("first"));
- System.out.println("isContain other:"+list.contain("other"));
- System.out.println("getdata1:"+list.getData(1));
- list.setData("none",0);
- list.printAll();
- list.deleteNode(0);
- list.printAll();
- list.deleteNode(1);
- list.printAll();
- System.out.println(list.size());
- list.deleteData("none");
- list.deleteData("third");
- list.printAll();
- System.out.println(list.size());
- list.deleteData("second");
- //list.deleteData("third");
- list.printAll();
- System.out.println(list.size());
- //System.out.println("getdata3:"+list.getData(3));
- }
- }
这个就是一个简单的实现,对于其中的一些算法的实现没有做比较深的研究。有时间去研究一下 java 实现 List 的源码。
来源: http://www.bubuko.com/infodetail-1969325.html