[学习交流] 模仿实现LinkedList(双向链表)

模仿实现LinkedList.最先使用了单链表进行模仿.但是每次进行增加和删除操作都要找前驱结点,比较麻烦.
这次使用一个双向链表进行模仿,这样每个结点记录了他的前驱和后继,比较方便. 代码如下:
/**
* Title: DoubleLinkedLinearList.java
* Description: 双向链表(带头节点) 
* Copyright: Copyright (c) 2015
* @version 1.0
*/
package com.dt.linearlist;

public class DoubleLinkedLinearList<T> implements ILinearList<T> {

private Node<T> header;
private Node<T> pre;
private int length;
public DoubleLinkedLinearList(){
header = new Node<T>();
}

@Override
public void destoryList() {
Node<T> pointer = header.next;
while(pointer != null){
header = null;
header = pointer;
pointer = header.next;
}
length = 0;
}

@Override
public boolean isEmpty() {
return length == 0;
}

@Override
public int length() {
System.out.println("length = "+length);
return length;
}

@Override
public T get(int index) {
if (!checkBounds(index)) {
throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
}

Node<T> pointer = getElement(index);

return pointer.item;
}

@Override
public boolean add(int index, T t) {
if (!checkBounds(index)) {
throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
}
System.out.println("add "+index+" "+t.toString());

Node<T> pointer = getElement(index);
Node<T> node = new Node<T>();
node.item = t;

node.next = pointer;
pointer.pre = node;

node.pre = pre;
pre.next = node;

length++;
return true;
}

@Override
public T delete(int index) {
if (!checkBounds(index)) {
throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
}

Node<T> pointer = getElement(index);

pre.next = pointer.next;
pointer.next.pre = pre;

pointer.next =null;
pointer.pre = null;
length--;
System.out.println("delete "+index+" "+pointer.item.toString());
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.item.toString());
sb.append("\n");
pointer = pointer.next;
}
sb.append("结束遍历单链表");
System.out.println(sb.toString());
return sb.toString();
}

@Override
public boolean add(T t) {
System.out.println("add "+t.toString());
Node<T> pointer = header.next;
pre = header;
while(pointer != null){
pre = pointer;
pointer = pointer.next;
}

Node<T > node = new Node<T>();
pre.next = node;
node.item = t;
node.pre = pre;
node.next = null;
length++;
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;
}

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;
}

private static class Node<T>{
Node<T> next;
Node<T> pre;
T item;
}
}

帐号		自动登录	找回密码
密码			加入黑马

[学习交流] 模仿实现LinkedList(双向链表)

0 个回复