JavaSE教程_进阶
单向链表
单向链表 ,即单链表. 每个存储单元至少有两个存储域, 一个用来存储数据, 一个域保存下个存储单元的引用。
各个存储单元的地址可以是不连续的。
插入/删除时不需要移动元素
通过单向链表实现线性表
/**
* 通过单向链表实现线性表
* @author 北京极悦老崔
*/
public class MySingleLink implements MyList {
private Node head; //头结点
private int size; //保存元素的个数
// 返回元素的个数
@Override
public int getSize() {
return size;
}
// 判断线性表是否为空
@Override
public boolean isEmpty() {
return size == 0 ;
}
// 在线性表中插入元素
@Override
public void insert(int i, Object e) {
//判断索引值是否越界
if ( i < 0 || i > size) {
throw new IndexOutOfBoundsException(i+"越界");
}
//创建结点
Node newNode = new Node(e, null);
//头结点为null的情况,链表不存在, 刚刚添加的结点就是头结点
if (head == null) {
head = newNode;
}else {
//在0位置插入结点
if (i == 0 ) {
newNode.next = head; //修改新结点的next域指向原来的头结点
head = newNode; //刚插入的结点就是新的头结点
}else {
//插入结点, 先找到i-1这个结点
Node pNode = head;
for( int x = 1; x<i; x++) {
pNode = pNode.next;
}
//注意,先修改新结点的next指针域, 再修改i-1结点的指针域
newNode.next = pNode.next;
pNode.next = newNode;
}
}
//元素个数加0
size++;
}
// 判断线性表中是否包含指定的元素
@Override
public boolean contains(Object e) {
return indexOf(e) >= 0 ;
}
// 返回元素e在线性表中第一次出现的索引值
@Override
public int indexOf(Object e) {
int i = 0 ; //保存元素e的索引值
Node pNode = head;
while( pNode != null) {
if ( e == null && pNode.data == null) {
return i;
}else if (e != null && e.equals(pNode.data)) {
return i;
}
i++;
pNode = pNode.next;
}
return -1;
}
//从线性表中删除第一个与e相同的元素
@Override
public Object remove(Object e) {
//找到元素e第一次出现的索引值
int index = indexOf(e);
if (index < 0 ) {
return null; //元素不存在
}
return remove(index);
}
//从线性表中删除指定索引的元素
@Override
public Object remove(int i) {
//判断是否越界
if (i < 0 || i >= size) {
throw new IndexOutOfBoundsException(i + "越界");
}
Node pNode = head;
//删除头结点
if (i == 0) {
head = head.next;
size--;
return pNode.data; //返回删除头结点的数据
}
//找到i-1结点
for( int x = 1; x < i ; x++) {
pNode = pNode.next;
}
//
Object old = pNode.next.data; //保存删除结点的数据
pNode.next = pNode.next.next; //修改i-1结点的next指针域 ,指向 i+1结点
size--;
return old;
}
// 把线性表中i索引值的元素替换 为e
@Override
public Object replace(int i, Object e) {
//判断是否越界
checkIndex(i);
//找到i结点
Node pNode = getNode(i);
Object old = pNode.data ; //保存原来的数据
pNode.data = e; //替换
return old;
}
// 返回线性表中i索引值的元素
@Override
public Object get(int i) {
checkIndex(i);
Node pNode = getNode(i);
return pNode.data;
}
//检查索引值是否越界
private void checkIndex(int i ) {
if (i < 0 || i >= size) {
throw new IndexOutOfBoundsException(i + "越界");
}
}
//定义一个方法,返回i索引值的元素
private Node getNode(int i) {
if ( i < 0 || i >= size) {
return null;
}
if (i == 0) {
return head;
}
//找到i结点
Node pNode = head;
for( int x = 1; x <= i ; x++) {
pNode = pNode.next;
}
return pNode;
}
// 在指定的元素p的前面插入元素e
@Override
public boolean insertBefore(Object p, Object e) {
//找p的位置
int index = indexOf(p);
if (index < 0 ) {
return false; //元素p不存在
}
insert(index, e);
return true;
}
// 在指定的元素p的后面插入元素e
@Override
public boolean insertAfter(Object p, Object e) {
// 找p的位置
int index = indexOf(p);
if (index < 0) {
return false; // 元素p不存在
}
insert(index+1, e);
return true;
}
//重写toString()
@Override
public String toString() {
// 把链表中各个结点的数据域连接起来
StringBuilder sb = new StringBuilder();
sb.append("[");
Node pNode = head;
while(pNode != null) {
sb.append(pNode.data);
//使用逗号分隔
if (pNode.next != null) {
sb.append(",");
}
pNode = pNode.next; //指针下移
}
sb.append("]");
return sb.toString();
}
//定义一个内部类表示单向链表中的结点
private class Node{
Object data; //保存数据
Node next; //下个结点的引用
public Node(Object data, Node next) {
super();
this.data = data;
this.next = next;
}
}
}
双向链表
单向链表只能通过一个结点的引用访问它的后续结点, 不能访问前驱结点, 如果要找某个 结点的前驱结点, 需要从头结点开始依次查找。
在双向链表中,扩展了结点的结构, 每个 结点除了存储数据外, 通过一个引用指向后续结点,再定义一个引用指向前驱结点：
双向链表的结构:
插入元素
/**
* 双向链表
* @author 北京极悦老崔
*/
public class MyDualLinkedList implements MyList {
private Node first; //指向头结点
private Node last; //指向尾结点
private int size; //保存元素的个数
// 返回元素的个数
@Override
public int getSize() {
return size;
}
// 判断链表是否为空
@Override
public boolean isEmpty() {
return size == 0 ;
}
// 在指定的索引值插入元素
@Override
public void insert(int i, Object e) {
//1)检查索引值是否越界
if (i < 0 || i > size) {
throw new IndexOutOfBoundsException(i + "越界");
}
//2) 如果i==0, 在头部添加元素
if ( i == 0 ) {
addFirst(e);
}else if( i == size ) {
//3) 如果i==size, 在尾部添加元素
addLast(e);
}else {
//4) 找到i结点, 在i结点的前面插入元素
Node pNode = getNode(i);
Node prevNode = pNode.prev;
//生成新的结点
Node newNode = new Node(e, prevNode, pNode);
//修改前驱结点的后续
prevNode.next = newNode;
pNode.prev = newNode;
size++;
}
}
//返回索引值对应的结点
private Node getNode(int i) {
//
Node pNode = first;
for( int x = 0 ; x < i; x++) {
pNode = pNode.next;
}
return pNode;
}
// 判断链表 中是否包含指定的元素e, 如果存在返回true
@Override
public boolean contains(Object e) {
return indexOf(e) >= 0;
}
// 判断元素e在链表中第一次出现的位置, 如果不存在该元素返回-1
@Override
public int indexOf(Object e) {
int i = 0 ; //保存元素e在链表中的索引值
//依次遍历链表中的各个结点, 比较结点的元素与指定的e是否一样
if (e == null) {
for( Node pNode = first; pNode != null ; pNode = pNode.next) {
if ( pNode.data == null ) {
return i;
}
i++;
}
}else {
for( Node pNode = first; pNode != null ; pNode = pNode.next) {
if ( e.equals(pNode.data) ) {
return i;
}
i++;
}
}
return -1;
}
// 从链表中删除指定的元素, 并返回删除的元素
@Override
public Object remove(Object e) {
//找到元素e对应的索引值
int index = indexOf(e);
if ( index < 0 ) {
return null;
}
return remove(index);
}
// 从链表中删除指定索引值的元素, 并返回删除的元素
@Override
public Object remove(int i) {
//判断索引值是否越界
checkIndex(i);
//找到i对应的结点
Node pNode = getNode(i);
Node prevNode = pNode.prev; //删除结点的前驱
Node nextNode = pNode.next; //删除结点的后续
if ( prevNode == null) {
//删除的头结点
first = nextNode;
}else {
prevNode.next = nextNode;
}
if ( nextNode == null) {
//删除尾结点
last = prevNode;
}else {
nextNode.prev = prevNode;
}
size--; //修改元素个数
return pNode.data;
}
//检查索引值是否越界
private void checkIndex(int i) {
if ( i < 0 || i >= size ) {
throw new IndexOutOfBoundsException(i + "越界");
}
}
// 修改指定索引值的元素, 把原来的元素返回
@Override
public Object replace(int i, Object e) {
//检查索引值是否越界
checkIndex(i);
//找到索引值为i的结点
Node pNode = getNode(i);
Object oldData = pNode.data;
pNode.data = e; //修改结点的元素
return oldData;
}
// 返回指定索引值的元素
@Override
public Object get(int i) {
//检查索引值越界
checkIndex(i);
//找到索引值为i的结点
Node pNode = getNode(i);
return pNode.data;
}
// 在指定的元素p前面插入元素e
@Override
public boolean insertBefore(Object p, Object e) {
//找到p元素在链表中的位置
int index = indexOf(p);
if (index < 0) { //链表中不存在元素p
return false;
}
insert(index, e); //在p元素的前面插入元素e
return true;
}
// 在指定的元素p后面插入元素e
@Override
public boolean insertAfter(Object p, Object e) {
// 找到p元素在链表中的位置
int index = indexOf(p);
if (index < 0) { // 链表中不存在元素p
return false;
}
insert(index + 1, e); // 在p元素的后面插入元素e
return true;
}
@Override
public String toString() {
// 依次遍历各个结点,把元素转换为字符串
StringBuilder sb = new StringBuilder();
sb.append("[");
for( Node node = first ; node != null ; node = node.next) {
sb.append( node.data );
//元素之间使用逗号分隔
if ( node != last ) {
sb.append(",");
}
}
sb.append("]");
return sb.toString();
}
//在链表中,经常会有针对头元素与尾元素的操作// 在链表的尾部添加元素
public void addLast(Object e) {
Node pNode = last;
//生成一个新的结点
Node newNode = new Node(e, last, null);
if (pNode == null ) {
first = newNode;
}else {
pNode.next = newNode;
}
last = newNode ;
size++;
}
//在头部添加元素e
public void addFirst(Object e) {
Node pNode = first;
// 生成一个新的结点
Node newNode = new Node(e, null, first);
first = newNode; //修改first指向新的结点
if ( pNode == null ) {
last = newNode;
}else {
pNode.prev = newNode;
}
size++; //元素的个数加1
}
//删除第一个元素, 删除头元素
public Object removeFirst() {
return remove(0);
}
//删除最后一个元素(尾元素)
public Object removeLast() {
return remove(size-1);
}
//返回头元素
public Object getFirst() {
return get(0);
}
//返回最后一个元素
public Object getLast() {
return get(size-1);
}
//定义一个内部类描述双向链表的结点
private class Node {
Object data;
Node prev; //指向前驱结点
Node next; //指向后继结点
public Node(Object data, Node prev, Node next) {
super();
this.data = data;
this.prev = prev;
this.next = next;
}
}
}
