java链表list_数据结构-List：使用Java实现双向链表LinkedList
JDK中的LinkedList屬于雙向循環鏈表.
下面是使用Java來實現一個雙向非循環鏈表.
package org.cgz.practice2;
import java.util.NoSuchElementException;
/**
* 雙向非循環鏈表
* @author cgz
* @param
*/
public class MyLinkedList {
/**
* 定義一個結點類
* @author cgz
* @param
*/
private static class Node {
private Node prev;
private Node next;
private E data;
public Node(E data, Node prev, Node next) {
this.data = data;
this.prev = prev;
this.next = next;
}
}
private Node head;
private Node tail;
private transient int size = 0;
public MyLinkedList() {
head = tail = null;
}
/** ------------------添加------------------ **/
public void add(E e) {
addLast(e);
}
/**
* 在index處插入一個元素
*
* @param index
* @param e
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("index:" + index + ",size:"+ size);
}
if (head == null) {// 當鏈表為空時,添加一個新結點
head = new Node(e, null, null);
tail = head;
} else {
if (index == 0) {// 在鏈表頭部插入元素
Node newNode = new Node(e, null, head);
head.prev = newNode;
head = newNode;
} else if (index == size) { // 在鏈表尾部插入
Node newNode = new Node(e, tail, null);
tail.next = newNode;
tail = newNode;
} else {
Node newNode = new Node(e, null, null);
Node current = getNodeByIndex(index);
current.prev.next = newNode;
newNode.prev = current.prev;
current.prev = newNode;
newNode.next = current;
}
}
size++;
}
/**
* 在鏈表頭添加元素
*
* @param e
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 在鏈表末尾添加元素
*
* @param e
*/
public void addLast(E e) {
add(size, e);
}
/**
* 根據index獲取所在位置的元素
* @param index
* @return
*/
private Node getNodeByIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("index:" + index + ",size:"+ size);
}
if(size==0) {
throw new NoSuchElementException();
}
Node current;
// 如果index在鏈表前半段,則從表頭開始查找
if (index <= size / 2) {
current = head;
for (int i = 1; i <= index; i++) {
current = current.next;
}
} else {
// 如果index在鏈表后半段,則從尾部查找
current = tail;
for (int i = size-1; i >= index+1; i--) {
current = current.prev;
}
}
return current;
}
/** ------------------刪除------------------ **/
public boolean remove(E e) {
int index = indexOf(e);
if(index!=-1) {
remove(index);
return true;
}
return false;
}
/**
* 根據index刪除元素
* @param index
* @return
*/
public E remove(int index) {
Node node = getNodeByIndex(index);
E old = null;
//刪除鏈表頭
if (index == 0) {
old = head.data;
head.next.prev = null;
head = head.next;
//刪除鏈表尾
} else if (index == size-1) {
old = tail.data;
tail.prev.next = null;
tail = tail.prev;
} else {
old = node.data;
node.prev.next = node.next;
node.next.prev = node.prev;
}
size--;
return old;
}
/**
* 刪除首元素
* @return
*/
public E removeFirst() {
return remove(0);
}
/**
* 刪除尾元素
* @return
*/
public E removeLast() {
return remove(size-1);
}
/**
* 清空鏈表
*/
public void clear() {
Node current = head;
while(current!=null) {
Node next = current.next;
current.prev = current.next = null;
current.data = null;
current = next;
}
size = 0;
}
/** ------------------修改------------------ **/
public E set(int index, E e) {
Node oldNode = getNodeByIndex(index);
E oldData = oldNode.data;
oldNode.data = e;
return oldData;
}
/** ------------------查詢------------------ **/
/**
* 返回index處的元素
* @param index
* @return
*/
public E get(int index) {
return getNodeByIndex(index).data;
}
/**
* 返回首元素
* @return
*/
public E getFirst() {
return get(0);
}
/**
* 返回最后一個元素
* @return
*/
public E getLast() {
return get(size-1);
}
/**
* 返回元素在鏈表中的位置
* @param e
* @return
*/
public int indexOf(E e) {
Node current = head;
int count = 0;
while(current!=null) {
if(current.data.equals(e)) {
return count;
}
current = current.next;
count++;
}
return -1;
}
/**
* 是否包含元素e
* @param e
* @return
*/
public boolean contains(E e) {
return indexOf(e)!=-1;
}
/**
* 鏈表是否為空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 鏈表長度
* @return
*/
public int size() {
return size;
}
/**
* 輸出鏈表中的所有元素
*/
public void print() {
System.out.print(this.getClass().getSimpleName() + "：[");
Node current = head;
while(current!=null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.print("]");
}
}
總結
以上是生活随笔為你收集整理的java链表list_数据结构-List：使用Java实现双向链表LinkedList的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java中给变量赋值_java中变量赋值
- 下一篇： java httpclient 302_