《手写集合框架》LinkedList篇

嘿嘿嘿，拖延症犯了，这几天不怎么想写代码，所以趁没事干就写写了。进入正文

还是老套路嘻嘻嘻，因为我之前写了那个准备篇，对node已经描述的从差不多了，所以我就不过多描述了。 直接贴完代码强行解释一波

.

一、定义接口

public interface newList<T> {    //定义泛型，因为Object可以存储任意类型，有时候我们需要								//用泛型 代替Object 	public void add(Object object);  //集合的添加方法 	public void add(int index,Object object);  //指定添加位置   	public int size();  //获取集合的长度  	public Object get(Integer i );  //获取下标的为i的元素  	public void remove(Object o);  //移除object对象  	public void remove(int index);  //移除size = index的元素  }

二、编写LinkedList类

1.定义属性

     private newNode first = null ;   //第一个节点  	private newNode last = null  ; //最后一个节点  	private int size = 0;  // 集合的长度 

newNode还记得撒，我们上次定义了一个newNode类，整个链表的核心就是它，其他的内容就是方法也都是围绕它改改上下指向，来实现增删

2. add 添加方法

@Override	public void add(Object t) {				newNode newnode = new newNode();  //创建一个新的节点  		if(first == null) { // 如果链表的第一个为空  			newnode.Prev = null;  			newnode.object = t;   //第一个节点赋值    			newnode.Next = null; 			first = newnode ; 			last = newnode;    //最后一个节点就是当前新增进来的，下次添加一个节点时，prev就指向last 		}else {			last.Next = newnode ; //我们要知道last是上一个节点			newnode.Prev  =  last ;  			newnode.object = t ;  			newnode.Next = null; 			last = newnode ;		}		size ++;  //长度增加  	}//节点遍历，拿到指定索引的元素  	private newNode Node(int index) {		newNode temp = null;  		if(first !=null) {			temp = first;  		}		for (int i = 0; i < index; i++) {				temp = temp.Next; 			}		//从第一个元素开始依次循环，直到拿到		return temp;	}@Override	public void add(int index, Object object) {		if(index == size) { //添加到最后 			newNode newnode = new newNode(); //新的元素			newnode.Prev = last;  			newnode.object = object;			last.Next = newnode;			last = newnode;  		}else {  //插入到x的之前 			newNode node = this.Node(index);    //找到插入前的元素			newNode newnode = new newNode();  // 			newNode prev = node.Prev;			newnode.Prev = node.Prev;  			newnode.object = object;  			newnode.Next = node;			if(node.Prev == null) {   //如果上指向为空，则它就是第一个				first = newnode;			}else {				prev.Next = newnode;  				node.Prev = newnode;			}			last.Next = newnode; 			last = newnode;		}		size ++ ;	}

我只讲一下，为什么将新的元素赋给last，因为我们把last当做了最后一个操作的，到时候我们添加的时候如果添加到最后一个，这个last就是指向的依据。

3.remove() 方法

 public void remove(int index) {		newNode newnode = Node(index);  		deleteNode(newnode);	}	@Override	public void remove(Object object) {		if(object ==null) {  //== null 也是可以存在链表的 所以我们不排除这种情况			for (newNode node = first; node != null; node = node.Next) {				if(node.object == null) {					this.deleteNode(node);				}			}		}else {			for (newNode node = first; node != null; node = node.Next) {				if(node.object.equals(object)) {					this.deleteNode(node);				}			}		}			}	//写一个公共的元素删除方法 	public void deleteNode(newNode newnode) {		 final Object object= newnode.object;	     final newNode next = newnode.Next;	     final newNode prev = newnode.Prev;		if(prev == null) {  //如果当前节点的Prev为空 则代表它本身是第一个 			first = next;		}else {  			  prev.Next = next;						  newnode.Prev = null;  		}				if(next == null) {//如果当前节点的Next为空 则代表它本身是最后一个 			last = prev; 		}else {			next.Prev = prev;            newnode.Next = null;		}		size -- ;       	}

4.get 方法

@Override	public Object get(Integer i){		if(i<0 || i>size) {  //不符合逻辑  			try {				throw new Exception();			} catch (Exception e) {				e.printStackTrace();			}		}		return Node(i).object;	}

• WeChat: lljb1218

.

.