本文行文思路结构
一. 线性表
二. Java中的指针
三. 表的简单链表实现
四. 表的各种基本操作 --- 增删改查
1. 图解分析
2. 代码实现
五. 完整代码Demo
六. 总结
一. 线性表
部分定义和解释见下面链接:
http://blog.csdn.net/menglanyingfei/article/details/71519202
二. Java中的"指针"
首先, 学过C++的人肯定知道, Java比C++更安全. 当然, 在这里, 你只需要知道, Java中的引用(Reference)是一种受限制的(C++中)指针!
三. 表的简单链表实现
如何懂C/C++中链表是如何实现? 对于Java实现则完全是大同小异!
C语言链表实现的参考:
http://blog.csdn.net/menglanyingfei/article/details/52710574
我们知道Java中的链表LinkedList是用双向链表来实现的.
所以, 关于自己实现的链表类MyLinkedList, 在类的设计上:
-
MyLinkedList类本身, 它包含到两端的链, 表的大小以及一些方法;
-
Node类, 它可能是一个私有的嵌套类. 一个节点包含数据以及前一个节点的链和到下一个节点的链, 还有一些适当的构造方法;
-
LinkedListedIterator类, 该类抽象了位置的概念, 是一个私有类, 并实现接口Iterator. 它提供了方法next(), hasNext(), remove()的实现. (如果初学Java, 关于集合框架的迭代器部分可跳过!)
MyLinkedList.png
四. 表的各种基本操作 --- 增删改查
1. 图解分析
具有头节点和尾节点的空双链表.png
addBefore方法.png
remove方法.png
2. 代码实现
增.png
删.png
改.png
查.png
五. 完整代码Demo
部分测试用例.png
MyLinkedList.java
package org.lxy.ds;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
/**
*
* @author lxy
*
* @param <E>
*/
public class MyLinkedList<E> implements Iterable<E> {
private int theSize; // 容器内元素的个数
private int modCount = 0; // Modified Count代表自从构造以来对链表所做改变的次数
private Node<E> beginMarker;
private Node<E> endMarker;
// 静态内部类Node实现节点之间的连接
private static class Node<E> {
public E data;
public Node<E> prev;
public Node<E> next;
public Node(E d, Node<E> p, Node<E> n) {
data = d;
prev = p;
next = n;
}
}
// 无参的构造方法, 构造一个MyLinkedList类的对象之前, 清空里面的元素
public MyLinkedList() {
clear();
}
public void clear() {
beginMarker = new Node<E>(null, null, null);
endMarker = new Node<E>(null, beginMarker, null);
beginMarker.next = endMarker;
theSize = 0;
modCount++;
}
// 下面的方法, 即对容器(MyLinkedList对象)的操作, 方法名大多见名知义
public int size() {
return theSize;
}
public boolean isEmpty() {
return size() == 0;
}
public boolean add(E x) {
add(size(), x);
return true;
}
public void add(int idx, E x) {
addBefore(getNode(idx), x);
}
public E get(int idx) {
return getNode(idx).data;
}
public E set(int idx, E newVal) {
Node<E> p = getNode(idx);
E oldVal = p.data;
p.data = newVal;
return oldVal;
}
public E remove(int idx) {
return remove(getNode(idx));
}
private void addBefore(Node<E> p, E x) {
Node<E> newNode = new Node<E>(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
}
private E remove(Node<E> p) {
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
modCount++;
return p.data;
}
private Node<E> getNode(int idx) {
Node<E> p;
if (idx < 0 || idx > size()) {
throw new IndexOutOfBoundsException();
}
if (idx < size() / 2) {
p = beginMarker.next;
for (int i = 0; i < idx; i++) {
p = p.next;
}
} else {
p = endMarker;
for (int i = size(); i > idx; i--) {
p = p.prev;
}
}
return p;
}
@Override
public Iterator<E> iterator() {
return new LinkedListItetator();
}
// MyLinkedList类中的内部Iterator类
private class LinkedListItetator implements Iterator<E> {
private Node<E> current = beginMarker.next;
private int expectedModCount = modCount;
private boolean okToRemove = false;
@Override
public boolean hasNext() {
return current != endMarker;
}
@Override
public E next() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (!okToRemove) {
throw new IllegalStateException();
}
E nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
@Override
public void remove() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (!okToRemove) {
throw new IllegalStateException();
}
MyLinkedList.this.remove(current.prev);
okToRemove = false;
expectedModCount++;
}
}
}
MyLinkedListTest.java
package org.lxy.ds;
/**
* @author menglanyingfei
* @date 2017-5-14
*/
public class MyLinkedListTest {
public static void main(String[] args) {
MyLinkedList<Integer> myLinkedList = new MyLinkedList<>();
myLinkedList.add(1);
myLinkedList.add(2);
myLinkedList.add(3);
myLinkedList.add(4);
myLinkedList.add(5);
System.out.println(myLinkedList.size()); // 5
System.out.println(myLinkedList.get(0)); // 1
System.out.println(myLinkedList.get(1)); // 2
System.out.println(myLinkedList.set(0, 15)); // 1, set方法返回之前被修改的旧值
System.out.println(myLinkedList.get(0)); // 15
System.out.println(myLinkedList.remove(0)); // 15
System.out.println(myLinkedList.get(0)); // 2
}
}
个人博客:(一个一直在坚持认真学习Java的大三学生)
博客地址
六. 总结
Java中实现链表, 非常类似C++中, 只要知道其中的对应关系和指针如何指向, 同时注意容器中元素的界限问题, 明白这个实现原理, 应该不难的!
参考
http://www.importnew.com/18968.html
http://www.cnblogs.com/ITtangtang/p/3948610.html
数据结构与算法分析-Java语言描述
一点感悟与您分享
最近一段时间, 突然发现了: 在文学上, 这句话很经典.
悲剧就是把美好的东西毁灭给人看. -- 鲁迅
生活中, 有各种开心与悲伤, 其实, 在人内心深处是有一种对美好事物的向往, 由于它的存在, 才产生了各种目标与信念. 但人真是一种奇怪的生物, 往往对自己现在或者所拥有的事物不太注意和爱惜, 只在失去之后, 才知道它的珍贵!
这或许, 谈不上一种毁灭, 但不懂得珍惜, 也是让现在的自己所拥有的美好事物一点一点地失去......
个人对生活和人生的一点思考, 也希望看到这段文字的您有所感触和思考!
网友评论