java数据结构
参考：数组、单链表和双链表介绍 以及 双向链表的C/C++/Java实现
主要有以下几种类型
单向链表双端链表有序链表双向链表有迭代器的链表
链表的效率
这里顺便谈下链表和数组相比效率的优越性.在表头插入和删除的速度都很快,因为只需要改变一下引用所以花费O(1)的时间.
平均起来查找,删除和在指定节点后插入数据都需要搜索一半的链结点.需要O(N)次比较和数组一样.然由于链表删除插入的时候
不需要像数组那种元素的移动.所以效率还是要优于数组.
还有一点就是链表的内存可以随时的扩展内存.而数组的内存是一开始就固定好的.这样就会导致数组的效率和可用性大大下降.
链表劣势在于随机访问，无法像数组那样直接通过下标找到特定的数据项
java代码实现
单向链表
package cn.zlz.structure;
public class LinkedList<V> {
private Node first;
private int size;
public LinkedList() {
super();
}
public Node<V>
insertFirst(V
value) {
Node<V> node =
new Node<V>(
value);
node.setNext(first);
first = node;
size++;
return node;
}
public Node<V>
get(
int index) {
if (
this.isEmpty()) {
throw new IndexOutOfBoundsException(
"链表为空");
}
if (index >= size) {
throw new IndexOutOfBoundsException(
"越界");
}
Node node = first;
while (index-- >
0) {
node = node.getNext();
}
return node;
}
public Node<V>
remove(
int index) {
if (
this.isEmpty()) {
throw new IndexOutOfBoundsException(
"链表为空");
}
if (index >= size) {
throw new IndexOutOfBoundsException(
"越界");
}
Node<V> removeNode =
null;
Node<V> pre =
null;
if (index ==
0) {
pre =
null;
removeNode = first;
first = removeNode.next;
}
else {
pre =
this.
get(index -
1);
removeNode = pre.next;
pre.next = removeNode.next;
}
if (--size <=
0) {
first =
null;
}
return removeNode;
}
public boolean
isEmpty() {
return first ==
null;
}
public int getSize() {
return size;
}
@Override
public String
toString() {
if (first ==
null) {
return "LinkedList ";
}
return "LinkedList [" + first.toString() +
"]";
}
class Node<V> {
private V
value;
private Node next;
public Node() {
super();
}
public Node(V
value) {
super();
this.
value =
value;
}
public V
getValue() {
return value;
}
public void setValue(V
value) {
this.
value =
value;
}
public Node
getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String
toString() {
return "Node [value=" +
value +
", next=" + next +
"]";
}
}
public static void main(String[] args) {
LinkedList<String> linkedList =
new LinkedList<String>();
linkedList.insertFirst(
"a");
linkedList.insertFirst(
"b");
linkedList.insertFirst(
"c");
linkedList.insertFirst(
"d");
linkedList.insertFirst(
"e");
linkedList.insertFirst(
"f");
System.
out.println(linkedList.toString());
LinkedList<String>.Node<String> node = linkedList.
get(
2);
System.
out.println(node.getValue());
LinkedList<String>.Node<String> removeNode = linkedList.remove(
0);
System.
out.println(linkedList.toString());
System.
out.println(node.getValue());
}
}
双端单向链表
package cn.zlz.structure;
public class DbPortLinkedList<V> {
private Node first;
private Node last;
private int size;
public DbPortLinkedList() {
super();
}
public Node<V>
insertFirst(V
value) {
Node<V> node =
new Node<V>(
value);
if (
this.isEmpty()) {
last = node;
}
node.setNext(first);
first = node;
size++;
return node;
}
public Node<V>
insertLast(V
value) {
Node<V> node =
new Node<V>(
value);
if (
this.isEmpty()) {
first = node;
last = node;
return node;
}
last.setNext(node);
last = node;
size++;
return node;
}
public Node<V>
get(
int index) {
if (
this.isEmpty()) {
throw new IndexOutOfBoundsException(
"链表为空");
}
if (index >= size) {
throw new IndexOutOfBoundsException(
"越界");
}
Node node = first;
while (index-- >
0) {
node = node.getNext();
}
return node;
}
public Node<V>
remove(
int index) {
if (
this.isEmpty()) {
throw new IndexOutOfBoundsException(
"链表为空");
}
if (index >= size) {
throw new IndexOutOfBoundsException(
"越界");
}
Node<V> removeNode =
null;
Node<V> pre =
null;
if (index ==
0) {
pre =
null;
removeNode = first;
first = removeNode.next;
}
else {
pre =
this.
get(index -
1);
removeNode = pre.next;
pre.next = removeNode.next;
}
if (--size <=
0) {
first =
null;
last =
null;
}
return removeNode;
}
public boolean
isEmpty() {
return first ==
null && last ==
null;
}
public int getSize() {
return size;
}
@Override
public String
toString() {
if (first ==
null) {
return "DbPortLinkedList ";
}
return "DbPortLinkedList [" + first.toString() +
"]";
}
class Node<V> {
private V
value;
private Node next;
public Node() {
super();
}
public Node(V
value) {
super();
this.
value =
value;
}
public V
getValue() {
return value;
}
public void setValue(V
value) {
this.
value =
value;
}
public Node
getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String
toString() {
return "Node [value=" +
value +
", next=" + next +
"]";
}
}
public static void main(String[] args) {
DbPortLinkedList<String> dbPortLinkedList =
new DbPortLinkedList<String>();
dbPortLinkedList.insertFirst(
"a");
dbPortLinkedList.insertFirst(
"b");
dbPortLinkedList.insertLast(
"c");
dbPortLinkedList.insertFirst(
"d");
dbPortLinkedList.insertLast(
"e");
dbPortLinkedList.insertFirst(
"f");
System.
out.println(dbPortLinkedList.toString());
DbPortLinkedList<String>.Node<String> node = dbPortLinkedList.
get(
2);
System.
out.println(node.getValue());
DbPortLinkedList<String>.Node<String> removeNode = dbPortLinkedList.remove(
0);
System.
out.println(dbPortLinkedList.toString());
System.
out.println(removeNode.getValue());
}
}
有序链表
package cn.zlz.structure;
/**
* 有序单向链表：链表中的数据按从小到大排列 持有一个首部节点
* 有序链表插入数据效率为O(N),但查找跟删除最大数据就是表头数据效率为O(1).所以在最小数据存储频繁,但又不需要快速插入的时候有序链表是个不错的选择.
*/
public class SortedLinkedList {
private Node first;
private int size;
public SortedLinkedList() {
super();
}
public Node
insertFirst(Integer value) {
Node node =
new Node(value);
Node pre =
null;
Node current = first;
while (current !=
null && current.getValue()<value) {
pre = current;
current=current.next;
}
if(pre ==
null){
first = node;
}
else{
pre.next = node;
}
node.next = current;
size++;
return node;
}
public Node
get(
int index) {
if (
this.isEmpty()) {
throw new IndexOutOfBoundsException(
"链表为空");
}
if (index >= size) {
throw new IndexOutOfBoundsException(
"越界");
}
Node node = first;
while (index-- >
0) {
node = node.getNext();
}
return node;
}
public Node
remove(
int index) {
if (
this.isEmpty()) {
throw new IndexOutOfBoundsException(
"链表为空");
}
if (index >= size) {
throw new IndexOutOfBoundsException(
"越界");
}
Node removeNode =
null;
Node pre =
null;
if (index ==
0) {
pre =
null;
removeNode = first;
first = removeNode.next;
}
else {
pre =
this.get(index -
1);
removeNode = pre.next;
pre.next = removeNode.next;
}
if (--size <=
0) {
first =
null;
}
return removeNode;
}
public boolean isEmpty() {
return first ==
null;
}
public int getSize() {
return size;
}
@Override
public String
toString() {
if (first ==
null) {
return "SortedLinkedList ";
}
return "SortedLinkedList [" + first.toString() +
"]";
}
class Node {
private int value;
private Node next;
public Node() {
super();
}
public Node(
int value) {
super();
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(
int value) {
this.value = value;
}
public Node
getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String
toString() {
return "Node [value=" + value +
", next=" + next +
"]";
}
}
public static void main(String[] args) {
SortedLinkedList sortedLinkedList =
new SortedLinkedList();
sortedLinkedList.insertFirst(
4);
sortedLinkedList.insertFirst(
2);
sortedLinkedList.insertFirst(
3);
sortedLinkedList.insertFirst(
5);
System.out.println(sortedLinkedList);
}
}
双向链表
package cn.zlz.structure;
public class DbLinkedList<V> {
private Node header;
private int size;
public DbLinkedList() {
super();
this.header =
new Node(
null,
null,
null);
this.header.next =
this.header;
this.header.pre =
this.header;
}
public Node<V>
insert(
int index,V
value) {
if (index > size) {
throw new IndexOutOfBoundsException(
"越界");
}
Node<V> current =
null ;
if(size ==
0){
current =
this.header;
}
else{
current =
get(index);
}
Node<V> node =
new Node<V>(
value,current.pre,current);
node.pre.next = node;
node.next.pre = node;
size++;
return node;
}
public Node<V>
insertFirst(
int index,V
value) {
return this.insert(
0,
value);
}
public Node<V>
insertLast(
int index,V
value) {
Node<V> node =
new Node<V>(
value,
this.header.pre,
this.header);
node.pre.next = node;
node.next.pre = node;
size++;
return node;
}
public Node<V>
get(
int index) {
if (size==
0 || index > size) {
throw new IndexOutOfBoundsException(
"越界");
}
Node<V> node =
null;
if(index>(size)/
2){
System.
out.println(
"从后往前找");
node =
this.header.pre;
int round = size-index;
while (round-->=
0) {
node = node.pre;
}
}
else{
System.
out.println(
"从前往后找");
node =
this.header.next;
while (index-->
0) {
node = node.next;
}
}
return node;
}
public Node<V>
remove(
int index){
if (size==
0 || index > size-
1) {
throw new IndexOutOfBoundsException(
"越界");
}
Node<V> toDelNode =
this.
get(index);
toDelNode.pre.next = toDelNode.next;
toDelNode.next.pre = toDelNode.pre;
size--;
return toDelNode;
}
public int getSize() {
return size;
}
public boolean
isEmpty() {
return size ==
0;
}
public Node
getHeader() {
return header;
}
public void setHeader(Node header) {
this.header = header;
}
public void setSize(
int size) {
this.size = size;
}
@Override
public String
toString() {
StringBuilder stringBuilder =
new StringBuilder();
Node header =
this.getHeader();
Node next = header.getNext();
stringBuilder.append(header.getPre().getValue()+
":"+header.getValue()+
":"+header.getNext().getValue());
while(next!=header){
stringBuilder.append(
" ");
stringBuilder.append(next.getPre().getValue()+
":"+next.getValue()+
":"+next.getNext().getValue());
next = next.next;
}
return stringBuilder.toString();
}
class Node<V> {
private V
value;
private Node pre;
private Node next;
public Node() {
super();
}
public Node(V
value, Node pre, Node next) {
super();
this.
value =
value;
this.pre = pre;
this.next = next;
}
public Node(V
value) {
super();
this.
value =
value;
}
public V
getValue() {
return value;
}
public void setValue(V
value) {
this.
value =
value;
}
public Node
getPre() {
return pre;
}
public void setPre(Node pre) {
this.pre = pre;
}
public Node
getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String
toString() {
return "Node [value=" +
value +
", pre=" + pre +
", next=" + next +
"]";
}
}
public static void main(String[] args) {
DbLinkedList<String> dbLinkedList =
new DbLinkedList<String>();
System.
out.println(dbLinkedList.toString());
dbLinkedList.insert(
0,
"a");
System.
out.println(dbLinkedList.toString());
dbLinkedList.insert(
1,
"b");
System.
out.println(dbLinkedList.toString());
dbLinkedList.insert(
2,
"b");
System.
out.println(dbLinkedList.toString());
dbLinkedList.insert(
1,
"c");
System.
out.println(dbLinkedList.toString());
dbLinkedList.insert(
4,
"d");
System.
out.println(dbLinkedList.toString());
dbLinkedList.insert(
0,
"e");
System.
out.println(dbLinkedList.toString());
System.
out.println(dbLinkedList.
get(
3).getValue());
System.
out.println(dbLinkedList.toString());
}
}
