一个LinkedList的实现,非java util 的实现,没有用java util容器,纯实现过程,主要看算法。
- /*
- * To change this template, choose Tools | Templates
- * and open the template in the editor.
- */
- package linkedlisttest;
- /**
- *
- * @author Lindily
- */
- public class LinkedList<E> {
- int size = 0;
- Node<E> head = new Node(null, null, null);
- public LinkedList() {
- head.next = head.previous = head;
- }
- public void add(E node) {
- //核心 循环双向链表
- Node<E> newNode = new Node(head.previous, node, head); //新节点的prev指向头结点的prev 新节点的next指向头结点
- newNode.previous.next = newNode; //调整,新节点的前一个的后一个
- newNode.next.previous = newNode; //调整,新节点的后一个的前一个
- size++;
- }
- public Node get(int index) {
- if (index < 0 || index >= size) {
- throw new IndexOutOfBoundsException("Index:" + index + ",size:" + size);
- }
- Node node = head;
- if (index < (size >> 1)) { //index转为二进制带符号向右移动一个bit,相当于index/2
- for (int i = 0; i <= index; i++) { //head是哑元,i<=index当index=0时,返回head.next
- node = node.next; //对头结点进行迭代
- }
- }else{
- for(int i=size;i>index;i--){
- node=node.previous;
- }
- }
- return node;
- }
- public int size() {
- return size;
- }
- public static void main(String[] args) {
- LinkedList list = new LinkedList();
- list.add(1);
- list.add(2);
- list.add(3);
- for (int i = 0; i < list.size; i++) {
- System.out.println(list.get(i).node);
- }
- }
- }
- class Node<E> {
- E node;
- Node<E> next;
- Node<E> previous;
- public Node(Node<E> previous, E node, Node<E> next) {
- this.node = node;
- this.next = next;
- this.previous = previous;
- }
- }
- /*
- * To change this template, choose Tools | Templates
- * and open the template in the editor.
- */
- package linkedlisttest;
- /**
- *
- * @author Lindily
- */
- public class SingleLinkedList<T> {
- int size = 0;
- Node<T> head, tail;
- public SingleLinkedList() {
- head = tail = null;
- }
- public void add(T node) {
- if (size == 0) {
- head = tail = new Node<T>(node, null);
- } else {
- tail.next = new Node<T>(node, null);
- tail = tail.next;
- }
- size++;
- }
- public Node<T> get(int index) {
- if (index < 0 || index >= size) {
- throw new IndexOutOfBoundsException("Index:" + index + ",size:" + size);
- }
- Node<T> node = head;
- for (int i = 0; i < index; i++) { //当index=0时,i不小于index(零不小于零),于是直接return头结点,与linkedList不同,head不是哑元
- node = node.next; //对头结点进行迭代
- }
- return node;
- }
- public int size(){
- return size;
- }
- public static void main(String[] args){
- SingleLinkedList list=new SingleLinkedList();
- list.add(1);
- list.add(2);
- list.add(3);
- for(int i=0;i<list.size();i++){
- System.out.println(list.get(i).node);
- }
- }
- }
- class Node<T> {
- T node;
- Node<T> next;
- public Node(T node, Node next) {
- this.node = node;
- this.next = next;
- }
- }
来源: http://www.phpxs.com/code/1002854/