集合学习之模仿LinkedList - 黑马程序员技术交流社区

/**
* Title: ILinearList.java
* Copyright: Copyright (c) 2015
* @author possible
* @version 1.0
*/
package com.dt.linearlist;
public interface ILinearList<T> {
// /**
// * 初始化线性表
// *
// * @return 返回线性表引用
// */
// public T initList();
/**
* 删除线性表
*
* @return 返回true 销毁成功 false失败
*/
public void destoryList();
/**
* 判断线性表是否为空
*
* @return true 链表为空. false 链表不为空
*/
public boolean isEmpty();
/**
* 线性表长度
*
* @return 链表长度
*/
public int length();
/**
* 获取指定索引线性表结点
*
* @param index
* 获取index位置的元素
* @return 返回元素 T
*/
public T get(int index);
/**
* 在指定位置插入元素
*
* @param i
* 插入位置的索引
* @param t
* 插入的元素
* @return true 插入成功, false 插入失败
*/
public boolean add(int index, T t);
/**
* 删除指定索引的元素
*
* @param i
* 删除指定位置的元素
* @return true 删除成功; false 删除失败
*/
public T delete(int index);
/**
* 线性表遍历
*
* @return 返回遍历结果
*/
public String traverse();
/**
* 插入元素结点.
*
* @param t
* 插入结点
* @return true 插入成功 ; false 插入失败
*/
public boolean add(T t);
}

复制代码

/**
* Title: LinkedLinearList.java
* @version 1.0
*/
package com.dt.linearlist;
public class LinkedLinearList<T> implements ILinearList<T> {
private Node<T> header;
private Node<T> tailer;
private Node<T> pre;
private int length;
public LinkedLinearList() {
header = new Node<T>();
tailer = header;
}
/**
* 销毁单链表.
*/
@Override
public void destoryList() {
Node<T> node = header;
while(header.next != null){
header = header.next;
node.next = null;
node.item = null;
node = header;
}
length = 0;
}
/**
* 单链表是否为空
*/
@Override
public boolean isEmpty() {
return length() == 0;
}
/**
* 单链表的长度
*/
@Override
public int length() {
System.out.println("length = " + length);
return length;
}
/**
* 获取指定索引出的Node
*/
@Override
public T get(int index) {
Node<T> node = getElement(index);
System.out.println(node.item);
return node.item;
}
/**
* 在指定索引位置添加Node
*/
@Override
public boolean add(int index, T t) {
if (!checkBounds(index)) {
throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
}
Node<T> node = new Node<T>();
node.item = t;
Node<T> pointer = getElement(index);
pre.next = node;
node.next = pointer;
increaseLength();
return true;
}
/**
* 删除指定位置的索引Node
*/
@Override
public T delete(int index) {
Node<T> pointer = getElement(index);
pre.next = pointer.next;
// 剪断pointer.next的对下一个结点的引用;
pointer.next = null;
decreaseLength();
return pointer.item;
}
/**
* 单链表遍历.
*/
@Override
public String traverse() {
StringBuffer sb = new StringBuffer();
sb.append("开始遍历单链表");
sb.append("\n");
if (header.next == null) {
sb.append("单链表无元素");
sb.append("\n");
sb.append("结束遍历单链表");
return sb.toString();
}
Node<T> pointer = header.next;
while (pointer != null) {
sb.append(pointer.toString());
sb.append("\n");
pointer = pointer.next;
}
sb.append("结束遍历单链表");
System.out.println(sb.toString());
return sb.toString();
}
/**
* 单链表添加元素.尾结点插入法
*/
@Override
public boolean add(T t) {
Node<T> node = new Node<T>();
node.item = t;
tailer.next = node;
tailer = node;
increaseLength();
return true;
}
// 得到指定位置的索引结点.
private Node<T> getElement(int index) {
if (!checkBounds(index)) {
throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
}
int counter = 0;
Node<T> pointer = header.next;
// 删除index的前一个结点
pre = header;
while (pointer != null) {
if (counter == index) {
break;
}
counter++;
// 未找到对应的索引,继续向下查找
pre = pre.next;
pointer = pointer.next;
}
return pointer;
}
/*
* 添加元素,链表长度增加1
*/
private void increaseLength() {
length++;
}
/*
* 删除元素,链表长度减1
*/
private void decreaseLength() {
length--;
}
private String checkBoundsMsg(int index) {
if (index >= length) {
return "下标越界 " + " length: " + length + " index: " + index;
}
return null;
}
/**
* 检查指定的索引是否越界
*
* @param index
* @return
*/
private boolean checkBounds(int index) {
return index >= 0 && index < length;
}
/**
* 单链表结点
*
* @author possible
*
*/
private static class Node<T> {
/**
* 下一个结点引用
*/
Node<T> next;
/**
* 存储的对象
*/
T item;
@Override
public String toString() {
return "Node [" + " item=" + item + "]";
}
}
}

复制代码